The classic McNugget problem states:
Chicken McNuggets can be purchased in quantities of 6, 9, and 20 pieces. You can buy exactly 15 pieces by purchasing a 6 and a 9, but you can't buy exactly 10 McNuggets. What is the largest number of McNuggets that can NOT be purchased?
The problem can be generalized to one of:
If you have an item that can be purchased in quantities of $a$, $b$, and $c$ ($a < b < c$, $gcd(a,b,c) = 1$), what is the largest integer $N$ of the item that cannot be purchased? (found by integers $x$, $y$, $z$ that satisfy $xa + yb + zc = N$)
In Computer Science class today, we were discussing general ways to solve this problem and one way is to find the smallest sequence of $a$ consecutive numbers that could all be formed by $xa + yb + zc$. Then the largest number that cannot be purchased is one less than the first of the $a$ consecutive numbers.
Our question was: how would you determine the starting point to try sequences of $a$ consecutive numbers? You do not want to start too low, or you will take a long time to find the solution, and you do not want to start too high, or you may miss the solution.
$\endgroup$ 77 Answers
$\begingroup$Let $a_1,\ldots,a_k$ be positive integers with $\operatorname{gcd}(a_1,\ldots,a_k)=1$. Then for all sufficiently large $N$, there are non-negative integers $x_1,\ldots,x_k$ such that
$a_1 x_1 + \ldots + a_k x_k = N$.
In fact, this paper gives an elementary discrete geometry proof that the number $r(N)$ of such solutions is asymptotic to $\frac{N^{k-1}}{(k-1)! a_1 \cdots a_k}$. Thus there is a well-defined conductor $\mathfrak{c}(a_1,\ldots,a_k)$, the least positive integer $c$ such that $r(N) \geq 1$ for all $N \geq c$.
Computing the conductor $c$ is callled the Diophantine Problem of Frobenius. Hundreds of papers have treated it. It is known that for each fixed $k$ there is a polynomial time algorithm for computing $\mathfrak{c}$. I believe this was first established in
R. Kannan, Lattice translates of a polytope and the Frobenius problem, Combinatorica 12 (1992), 161-177.
In the $k = 3$ case that you are asking about, an earlier paper of Harold Greenberg gives an algorithm which is simpler, and (if I am not mistaken) faster than that of the general case.
Finally, rather recently Ramirez-Alfonsin wrote a whole book on the Frobenius problem. The information contained therein may well be more comprehensive and/or up to date than mine.
$\endgroup$ 7 $\begingroup$If you're looking for a number $n$ to start determining the number of representations of $n$,$n+1$,$n+2$,$\ldots$ until you get a run of $a_1$ consecutive integers with positive representations and want to be certain that your $n$ is the smallest such number, this is equivalent to asking for a lower bound on the conductor $\mathfrak{c}(a,b,c)$ as defined in my previous post. In three variables, it is known that
$\mathfrak{c}(a,b,c) \geq \sqrt{3abc} - a - b - c + 1$,
so you may start checking there. The inequality comes from the following paper.
$\endgroup$ 3 $\begingroup$J. L. Davison, On the Linear Diophantine Problem of Frobenius, J. Number Theory, 48 (1994), no. 3, 353–363.
The case of 2 sizes was given as a problem of putting stamps on letters by Sylvester. If the stamp denominations are $p$ and $q$, with $\gcd(p,q) = 1$, Alexander Bogomolny has a nice proof that the maximal non-representable number is $A(p, q) = p q - p - q$.
Form the family of arithmetic sequences: $$ \begin{align*} f_0 &= 0 + 0 q, 0 + 1 q, 0 + 2 q, \ldots \\ f_1 &= 1 + 0 q, 1 + 1 q, 1 + 2 q, \ldots \\ \vdots \\ f_{p - 1} &= p - 1 + 0 q, p - 1 + 1 q, p - 1 + 2 q, \ldots \end{align*} $$ As $\gcd(p, q) = 1$, the sequences are disjoint and their union is all the numbers representable as $x p + y q$. The following generating function represents the set: $$ F(z) = \frac{1}{1 - z^q} (1 + z^p + z^{2 p} + \dotsb + z^{(q - 1) p}) = \frac{1 - z^{p q}}{(1 - z^p) (1 - z^q)} $$ The set $\mathbb{N}_0$ is just: $$ N(z) = \frac{1}{1 - z} $$ The difference is a polynomial whose exponents give the non-representable numbers: $$ N(z) - F(z) = \frac{(1 - z^p) (1 - z^q) - (1 - z) (1 - z^{p q})} {(1 - z) (1 - z^p) (1 - z^q)} $$ By subtracting degrees we get the degree of the polynomial, i.e., $A(p, q) = p q - p - q$.
If you have $a$, $b$, and $c$ pairwise relatively prime, then $A(a, b, c) \le \min\{A(a, b), A(a, c), A(b, c)\}$
$\endgroup$ 3 $\begingroup$For the McNugget Problem, we have the equation 6a+ 9b + 20c. First considering the two terms 6a + 9b = 3(2a+3b). Now from the answer for two variables case, we see that 2a+3b = (2-1)(3-1) + t = 2 + t for some t greater than or equal to 0. Hence the original equation now becomes 3(2+t) + 20c = (3t+20c) + 6. Again applying the two variable formula for the terms in brackets we see that 3t + 20c = (3-1)(20-1)+ s = 38 + s for some s greater than or equal to 0. So the given equation can now be written as 6a+ 9b + 20c = (38+s) + 6 = 44 + s for all s, greater than or equal to zero. So the given expression produces all numbers from 44 and so 43 is the largest number with the desired property.
$\endgroup$ $\begingroup$This specific case is discussed in Wikipedia on the coin problem, where it is shown the maximum that cannot be purchased is $43$.
$\endgroup$ 1 $\begingroup$It's well after this post has been published and I know only a little about the topic, but if the question is only where to start the program that should be pretty simple:
First note the formula to solve the problem in two variables: Find the minimal N such that $$ ax + by \neq N $$ Theorem: N = ab - a - b = (a - 1)*(b - 1) - 1
WLOG assume a < b.
Reducing mod a, we only need to find the point where every congruence class in a is finally filled, and then subtract a.
Since we only have one other number, b, simply compute r such that $ r + b \equiv 0 $ to find the last number that occurs in the series of adding b to itself mod a. At that number, the last congruence class will be filled, so we know that $ N \equiv r $ (mod a)
Now we know that the b had to be added up to the value of the second to last congruence, and that adding b's value a times to itself will yield ab, which is equivalent to 0 mod a. It follows that r represents ab - b in the integers.
This number is the first number such that every value after it will be filled, because we know ab is solved and every congruence class after ab - b will be filled by adding b to itself modulo a. Therefore, ab - b - a is the first number that CAN'T be made.
If we have more than two kinds of boxes of McNuggets, then the answer we get must be less than ab - a - b, since if we only had those two we could McCalculate them to our hearts' content.
Introducing a third number complicates this method when b and c are far apart, because we will have to decide if it is easier to add by the bigger number or the smaller number modulo a. But we can only add each of them a finite number of times, and how many c values we can add in before we bust ab - a - b can easily be computed. Once we ascertain the hardest congruence class/classes to make, it merely becomes a matter of which way it is made with b and c modulo a to see if it is the easiest.
Hopefully that gives a concise and elementary way to answer the question forever and for all amounts of inputs.
$\endgroup$ $\begingroup$For any two numbers a and b, the largest number that cannot be written as linear combination of the expression ma + nb is lcm(m,n) - m - n. In the case if m,n are relatively prime, then lcm(m,n) = mn and so we get the usual McNugget Problem answer.
$\endgroup$
