Frobenius problem

The Frobenius number is the largest value b for which the Frobenius equation a_1 x_1 + a_2 x_2 + ... + a_n x_n = b, 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}].

coin problem | Frobenius equation | greedy algorithm | McNugget number | postage stamp problem