Solving Frobenius Equations and Computing Frobenius Numbers

A Frobenius equation is an equation of the form:$$a_1x_n + \ldots + a_nx_n=m$$where \( a_1, \dots, a_n \) are positive integers, \( m \) is an integer and the coordinates \(x_1, \dots, x_n \) of solutions are required to be non-negative integers.

The Frobenius number of \( a_1, \ldots, a_n \) is the largest \( m \) for which the Frobenius equation \(a_1x_n + \ldots + a_nx_n=m \) has no solutions.

These definitions were taken from the Wolfram Language & System Documentation Center Tutorial. A Frobenius equation and number are both seemingly abstract concepts but there are practical, concrete applications. In the tutorial, the following example is given: in how many ways can a total of 42 cents be created using 1, 5, 10, and 25 cent coins? The problem can be expressed as a Frobenius equation:$$x_1+5x_2+10x_3+25x_4=42$$WolframAlpha solves this using the command: FrobeniusSolve[{1, 5, 10, 25}, 42] and the following output is produced:

{{2, 0, 4, 0}, {2, 1, 1, 1}, {2, 2, 3, 0}, {2, 3, 0, 1}, {2, 4, 2, 0}, {2, 6, 1, 0}, {2, 8, 0, 0}, {7, 0, 1, 1}, {7, 1, 3, 0}, {7, 2, 0, 1}, {7, 3, 2, 0}, {7, 5, 1, 0}, {7, 7, 0, 0}, {12, 0, 3, 0}, {12, 1, 0, 1}, {12, 2, 2, 0}, {12, 4, 1, 0}, {12, 6, 0, 0}, {17, 0, 0, 1}, {17, 1, 2, 0}, {17, 3, 1, 0}, {17, 5, 0, 0}, {22, 0, 2, 0}, {22, 2, 1, 0}, {22, 4, 0, 0}, {27, 1, 1, 0}, {27, 3, 0, 0}, {32, 0, 1, 0}, {32, 2, 0, 0}, {37, 1, 0, 0}, {42, 0, 0, 0}}

The Frobenius number is found using FrobeniusNumber[{1, 5, 10, 25}] which yields in this case -1. This is presumably WolframAlpha's way of saying that for this situation there is no such number because one of the building blocks is 1 and that can be used to build any positive integer. Let's look at another Frobenius equation:$$12x_1+16x_2+20x_3+27x_4=123$$Here FrobeniusSolve[{12, 16, 20, 27}, 123] yields:

{{0, 1, 4, 1}, {0, 6, 0, 1}, {1, 4, 1, 1}, {2, 2, 2, 1}, {3, 0, 3, 1}, {4, 3, 0, 1}, {5, 1, 1, 1}, {8, 0, 0, 1}}

The Frobenius number in this case (found using FrobeniusNumber[{12, 16, 20, 27}]) is 89. The actual output is {}. It can be noted that FrobeniusSolve[{12, 16, 20, 27},73]) also produces {} as output but 73<89 and so 73 is not the Frobenius number for the equation. What this means is that the Frobenius equation \(12x_1+16x_2+20x_3+27x_4=m \) always has a solution provided \(m>89\).

Here is a link to the MacTutor archive page about Ferdinand Georg Frobenius. I haven't yet found how to solve Frobenius equations or calculate a Frobenius number in SageMath. The only reference I've found is the following (link) which is clearly not the same:

We can compute the Frobenius coordinates and go back and forth: 

sage: Partition([7,3,1]).frobenius_coordinates()
([6, 1], [2, 0]) 

sage: Partition(frobenius_coordinates=([6,1],[2,0]))
[7, 3, 1] 

sage: all(mu == Partition(frobenius_coordinates=mu.frobenius_coordinates())
....:     for n in range(30) for mu in Partitions(n))
True