The Frobenius problem

Definition

Given a positive integers set {a1, a2, ... ap}, the Frobenius problem asks what is the largest integer N for which the equation a1.x1 + a2.x2 + .. + ap.xp = N has no positive integers {x1, x2, ... xp} solution. If the p numbers {a1, a2, ..., ap} are prime in their set, then this largest integer called the Frobenius number is well defined and is denoted g(a1, a2, ... ap).This problem is also known as the coin problem since the Frobenius number of a set {a1, a2, ... ap} can be seen as the largest money amount that cannot be obtained using only coins of given denominations {a1, a2, ... ap}.

If a1= 6, a2= 9 and a3= 20, the list of number N for which the equation 6x1+9x2+20x3 = N has no positive integer solution is called the non McNugget numbers. The list is {1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43} and is refered as sequence A065003 in OEIS. Mc Donald sells chicken McNugget in boxes of 6, 9 and 20, so the non McNugget numbers are the numbers of McNuggets you cannot get buying any number of boxes.

Calculator

There are 2 options with the following calculator:

• When the first radio button is checked, the calculator provides the Frobenius number g(a1, a2, ... ap) of the set {a1, a2, ... ap}, the list of all integers N for which the equation a1.x1 + a2.x2 + .. + ap.xp = N has no positive integer solution and the number NRI(a1, a2, ... ap) of such non-representable integers.

• When the second radio button is checked, the calculator solves the equation a1.x1 + a2.x2 + .. + ap.xp = N for a given N.

1 Find g(a1, a2, ... ap), NRI(a1, a2, ... ap) and all integers N for which equation a1.x1 + a2.x2 + .. + ap.xp = N has no positive integer solutions
2 Find all solutions to equation a1.x1 + a2.x2 + .. + ap.xp = N

Enter a list of integers a1, a2, ... ap separated by a comma or a space, N if needed, and click on "Go !" button

References

The Frobenius problem on Wikipedia
Schur's theorem: Used to prove that g(a1, a2, ... ap) is defined if and only if GCD(a1, a2, ... ap) = 1

Return to table of content