TOPICS
Search

Frobenius Number


The Frobenius number is the largest value b for which the Frobenius equation

 a_1x_1+a_2x_2+...+a_nx_n=b,
(1)

has no solution, where the a_i are positive integers, b is an integer, and the solutions x_i are nonnegative integer. As an example, if the a_i values are 4 and 9, then 23 is the largest unsolvable number. Similarly, the largest number that is not a McNugget number (a number obtainable by adding multiples of 6, 9, and 20) is 43.

Finding the Frobenius number of a given problem is known as the coin problem.

Computation of the Frobenius number g(a_1,a_2,...) is implemented in the Wolfram Language as FrobeniusNumber[{a1, ..., an}].

Sylvester (1884) showed

g(a_1,a_2)=(a_1-1)(a_2-1)-1
(2)
=a_1a_2-(a_1+a_2).
(3)

See also

Coin Problem, Frobenius Equation, Greedy Algorithm, McNugget Number, Postage Stamp Problem

Explore with Wolfram|Alpha

References

Sylvester, J. J. "Question 7382." Mathematical Questions from the Educational Times 41, 21, 1884.

Referenced on Wolfram|Alpha

Frobenius Number

Cite this as:

Weisstein, Eric W. "Frobenius Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FrobeniusNumber.html

Subject classifications