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.
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