General McNugget problem

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.

-
Undoubtedly you have read about Frobenius coin problem (they discuss the McNugget problem there). The mathematical umbrella concept is that of numerical semigroups. –  Jyrki Lahtonen Mar 25 '13 at 16:53
I'm curious as to why this question has a downvote? –  Pete L. Clark Mar 25 '13 at 17:13
I am as well... –  SSumner Mar 25 '13 at 17:18
I believe General McNugget was a civil war hero. –  Grumpy Parsnip Mar 26 '13 at 15:50

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)\}$

-
So what you're saying is if my three numbers are pairwise relatively prime, I could find the minimum of $A(a,b),A(a,c),A(b,c)$ and work backwards from there finding $a$ consecutive numbers that can be formed by $x_1a+x_2b+x_3c$? –  SSumner Mar 25 '13 at 19:18
@SSummer, That certainly is an upper bound, no clue how tight. –  vonbrand Mar 25 '13 at 19:22
thanks! This should help –  SSumner Mar 25 '13 at 19:25
It feels a little misleading to call $F(z)$ a generating function per se; it's true that it's an indicator function for the set, but it's a membership function rather than a counting function and so many of the usual generating function transforms couldn't be applied to it. (But of course, the fact that it represents the set and not just a count allows the manipulations below.) –  Steven Stadnicki Mar 26 '13 at 16:06

Let $a_1,\ldots,a_k$ be positive integers with $\operatorname{gcd}(a_1,\ldots,a_k)$. 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.

-
I don't believe this is what I'm looking for either. If I understand this right, the conductor $c$ is simply the smallest integer $N$, and all $N \geq c$ have solutions of the form $a_1x_1 + ... + a_kx_k$? I'm looking for how to choose the starting point to begin checking sequences of $a$ consecutive numbers without starting too low and being assured of finding the highest number that is not a solution. –  SSumner Mar 25 '13 at 17:21
@SSumner: Your underlying assumption is that you want to to solve the problem by starting at some $N$ and simply searching above it for sequences of $a_1$ consecutive represented numbers. This will give you an upper bound on the conductor, but (i) the true conductor might be smaller, and (ii) it is much, much slower than other algorithms. –  Pete L. Clark Mar 25 '13 at 19:37
@PeteLClark - I realize that it is slow, but I'm not interested in speed - we were merely discussing ways to solve this problem, and this was one of the ways. More of an interest problem than a useful problem –  SSumner Mar 25 '13 at 19:40
More fundamentally, you're asking a question of the form: "I have a very naive algorithm to solve the problem [here, start at $1$ and check until you get a sequence of $a_1$ represented integers]. Adjusting this parameter in my algorithm might make it work better [or might make it fail entirely]. What is the optimal value to set my parameter to?" I'm saying: here's a different algorithm which is much faster in all cases. I hope that you can appreciate the merit of that as a CS student. –  Pete L. Clark Mar 25 '13 at 19:40
@SSumner: You write "I'm not interested in speed" but your initial post says "You do not want to start too low, or you will take a long time to find the solution." I think you mean that you are interested only in the method you have come up with and not other, better methods to solve the problem. In that case, I agree that my answer is not very helpful to you, but I hope it will be helpful to others who read this post. –  Pete L. Clark Mar 25 '13 at 19:42

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.

J. L. Davison, On the Linear Diophantine Problem of Frobenius, J. Number Theory, 48 (1994), no. 3, 353–363.

-
Where do the variables $a_1$, $a_2$, and $a_3$ come from? –  SSumner Mar 25 '13 at 20:10
Sorry: they are your $a$, $b$ and $c$. –  Pete L. Clark Mar 26 '13 at 15:44
Okay, thanks. This should help as well –  SSumner Mar 26 '13 at 15:46

This specific case is discussed in Wikipedia on the coin problem, where it is shown the maximum that cannot be purchased is $43$.

-
I'm not asking for the answer to the McNugget problem. I am aware that the answer is 43 (using the method discussed, you can prove it by showing that $44$, $45$, $46$, $47$, $48$, and $49$ can all be formed by the relevant numbers. I'm asking in general, how would you pick a starting point to find the solution in this manner? –  SSumner Mar 25 '13 at 17:07