machine-checked

The McNugget Number

When McDonald's sold Chicken McNuggets only in boxes of 6, 9, and 20, some order totals were impossible: no combination of those boxes makes 43. But every total from 44 upward can be made. The largest impossible total — 43 — is the McNugget number. Try to buy any number below; then read why 43 is the wall, proved for every total at once, checked by a machine.

Here are three boxes: a 6-pack, a 9-pack, and a 20-pack. Pick any number of nuggets you'd like to order. Can the counter fill it exactly, with no nugget over and none short? For most numbers, yes. For twenty-two of them, no — and there is a largest one, past which the answer is always yes, forever.

Every total 0–71, grouped by remainder when divided by 6

Notice the columns. Reading down each one, the impossible reds give way to buyable golds and never turn back — because once you can make a total, you can make it plus another 6-pack, and another, forever. The wall in each column is its last red. The leftmost columns turn gold early; the column of numbers that leave remainder 1 (…31, 37, 43, 49…) holds out the longest, all the way to 43, and that is why 43 is the last impossible number anywhere.

The twenty-two you cannot buy

Enumerated live by the script on this page — every total from 1 upward with no exact box combination:

Twenty-two numbers, and then never again. The largest, 43, is the McNugget number. In the language of the mathematics, {6, 9, 20} generate a numerical semigroup; 43 is its Frobenius number and 22 is its genus — the count of gaps.

Why the wall is exactly 43

Six is the smallest box, so here is a shortcut to reaching every large total. Sort the numbers by their remainder mod 6 — that's the six columns above. Within a column, every entry is 6 apart, so if you can buy the smallest total in that column, you can buy all the bigger ones by adding 6-packs. The smallest buyable total in each column is:

Five of the six columns open up at or below 40. The stubborn one is remainder 1: its smallest buyable total is 49, because to leave remainder 1 mod 6 you need the 9 and the 20s to conspire, and the cheapest way is one 9 and two 20s. So the last impossible total is the number just below 49 in that column — 43. Every total from 44 up sits at or above its column's opening and is therefore buyable. There is no larger gap, ever.

This is the coin problem

Strip away the nuggets and it's a classic question, the Frobenius (or "coin") problem: given coins of fixed values, what is the largest amount you cannot pay exactly? For just two coin sizes that share no common factor, say a and b, there's a tidy formula — the largest unpayable amount is a·b − a − b. (This two-number case is the one competition math calls the "Chicken McNugget Theorem" (Sylvester gave the two-coin formula in 1882). For three sizes like 6, 9, and 20 there is no known general formula; you have to work it out, and 43 is the answer for this set. You can't shortcut it through a sub-pair either — 6 and 9 aren't coprime, so the two-coin formula doesn't apply to them.

The number 20 is what makes it interesting. With boxes of 6 and 9 alone you could only ever buy multiples of 3, so infinitely many totals stay impossible and there is no largest gap at all. The 20-pack — sharing no factor with 3 — is what finally lets the boxes reach every remainder, and so caps the impossible totals at 43.

The check

Two checks, at two strengths. On this page, the script searches for an exact box combination for every total and reports what it finds: the twenty-two impossible totals above, and 43 as the largest — That is corroboration, but a search can only ever test totals up to some ceiling.

The proof removes the ceiling. In research/mcnugget/lean/McNugget.lean the claim is proved in Lean 4 — with zero imports, so the only trusted component is Lean's kernel — for all totals at once: 43 is unbuyable, and every total ≥ 44 is buyable (a construction, not a search — the mod-6 argument above, made mechanical). The twenty-two gaps are each certified, and every buyable total below 44 is given an explicit receipt, so the census is complete with nothing sampled. The kernel reports the proof rests on nothing but Lean's two foundational axioms:

'McNugget.mcnugget_number' depends on axioms: [propext, Quot.sound]

No sorry, no Classical.choice, no native_decide. Reproduce it: bash research/mcnugget/lean/verify.sh (typechecks the file and asserts the axiom footprint), or the finite search alone with node research/mcnugget/verify.mjs.

Where honesty lives here

The mathematics is exact and eternal: for the set {6, 9, 20}, 43 is the Frobenius number and there are 22 gaps — proved, not asserted (and catalogued in OEIS as A065003, "Not McNugget numbers"). The story is a chosen model. Boxes of 6, 9, and 20 are the sizes the classic problem uses — they match the United Kingdom lineup, where the distinctive 9-piece box lived alongside the 6 and the 20-piece ShareBox. But menus change, and the answer changes with them: add a 4-piece (Happy Meal) size and the largest impossible total collapses from 43 to just 11; and in places where a 10-piece replaces the 9, every box size is even, so every odd total is forever impossible and there is no largest one at all. So "43" belongs to the pack set {6, 9, 20}, not to any current menu.

The nickname "McNugget number" was introduced by the mathematics educator Henri Picciotto — as a puzzle in Games Magazine in 1987, then in his textbook Algebra: Themes, Tools, Concepts (Wah & Picciotto, 1994) — though a competing account traces the framing to a 1990 rec.puzzles thread and Ilan Vardi's 1991 Computational Recreations in Mathematica, so we don't claim a single uncontested coinage. The underlying result is the general Frobenius (coin) problem, studied long before nuggets — Sylvester gave the two-coin formula in 1882. What is machine-checked here is the number theory; the McDonald's framing is the doorway, and it is labelled as one.