The Frobenius problem


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.


There are 2 options with the following calculator:

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


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