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.

Order this many nuggets

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 other columns turn gold sooner; 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:

rem 0 → 0 (buy nothing)
rem 1 → 49 = 9 + 20 + 20
rem 2 → 20 = 20
rem 3 → 9 = 9
rem 4 → 40 = 20 + 20
rem 5 → 29 = 9 + 20

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's 1882 paper counts the unpayable amounts, (a−1)(b−1)/2, and the formula itself is usually credited to him too.) For three sizes like 6, 9, and 20 there is no simple closed-form 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 only two of Lean's three standard axioms:

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

No sorry, no Classical.choice, no native_decide. Reproduce it: download lean/McNugget.lean and lean/verify.sh into a folder named lean and run that script with bash (it typechecks the file and fails unless every footprint is exactly [propext, Quot.sound]), or the finite search alone with research/mcnugget/verify.mjs and Node (put it beside that lean folder and, if Lean is installed, it runs the kernel check too).

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 McNuggets puzzle was introduced by the mathematics educator Henri Picciotto, as "Math McPuzzle" in Games Magazine in 1987, and a nugget version of it appears in his textbook Algebra: Themes, Tools, Concepts (Wah & Picciotto, 1994). Neither text uses the name "McNugget number". MathWorld's references for the term also include a 1990 rec.puzzles posting and Ilan Vardi's 1991 Computational Recreations in Mathematica, so we don't claim to know who coined it. The underlying result is the general Frobenius (coin) problem, studied long before nuggets: Sylvester counted the two-coin gaps in 1882. What is machine-checked here is the number theory; the McDonald's framing is the doorway, and it is labelled as one.

Corrected 2026-10-13 (claims pass): This page said Henri Picciotto introduced the nickname "McNugget number"; he introduced the puzzle ("Math McPuzzle", Games, 1987), and neither of the two texts it cited uses the name. It said Sylvester gave the two-coin formula in 1882; his 1882 paper counts the unpayable amounts, (a−1)(b−1)/2, and we found no statement of a·b − a − b in it. It said verify.sh asserts the axiom footprint; it only printed it, and exited 0 with a proof replaced by sorry. It now fails unless every footprint is exactly [propext, Quot.sound]. Smaller fixes: Lean has three standard axioms, not two; formulas for three box sizes exist, though no simple closed form; the slowest column is second from the left; and the files a reader needs are now linked, where the page had named paths in a repository a reader cannot open.