xxxii. Chicken McNugget (Frobenius Coin Problem)

Problem. Nuggets come in packs of $a$ and $b$ with $\gcd (a,b)=1$. What is the largest amount you cannot buy, and how many amounts are impossible?

Answer: the largest is $ab-a-b$ (Sylvester), and there are $\frac{(a-1)(b-1)}{2}$ impossible amounts. With packs $6,9,20$ the largest impossible amount is $43$.

long long frobenius(long long a, long long b) { return a * b - a - b; }        // gcd(a, b) = 1
long long gapCount(long long a, long long b) { return (a - 1) * (b - 1) / 2; }  // non-representable amounts

Proof: Sylvester's formula and the gap count

Every integer $N$ has a unique representation $N=xa+yb$ with $0\le x<b$ (since $a$ is invertible mod $b$); $N$ is representable with non-negative coefficients iff that $y\ge 0$. For $N=ab-a-b$, the representation is $x=b-1$, $y=-1$, so it is not representable; for any larger $N$, the unique $x\in [0,b)$ gives $yb=N-xa>ab-a-b-(b-1)a=-b$, so $y\ge 0$. Count. The map $N\mapsto ab-a-b-N$ sends representable to non-representable numbers and vice versa on $[0,ab-a-b]$ (if both were representable, their sum $ab-a-b$ would be), so exactly half of these $(a-1)(b-1)$ numbers are impossible. Checked by a DP for all coprime $a,b\le 15$. More than two pack sizes: shortest paths modulo the smallest pack (Congruences).