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.

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.

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.