General McNugget problem

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.

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