page_title: Coin problem
section_title: McNugget numbers
hierarchical_section_title: Coin problem / Examples / McNugget numbers
caption_attribution_description: Photo of a 20-piece box of McDonald's Chicken McNuggets.
context_page_description: The coin problem is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations has no common divisor greater than 1.
  There is an explicit formula for the Frobenius number when there are only two different coin denominations, x and y: xy − x − y. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time. No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP-hard.
context_section_description: One special case of the coin problem is sometimes also referred to as the McNugget numbers. The McNuggets version of the coin problem was introduced by Henri Picciotto, who included it in his algebra textbook co-authored with Anita Wah.  Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working the problem out on a napkin. A McNugget number is the total number of McDonald's Chicken McNuggets in any number of boxes. In the United Kingdom, the original boxes (prior to the introduction of the Happy Meal-sized nugget boxes) were of 6, 9, and 20 nuggets.
  According to Schur's theorem, since 6, 9, and 20 are relatively prime, any sufficiently large integer can be expressed as a (non-negative, integer) linear combination of these three.  Therefore, there exists a largest non-McNugget number, and all integers larger than it are McNugget numbers. Namely, every positive integer is a McNugget number, with the finite number of exceptions:
  1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43 (sequence A065003 in the OEIS).
  Thus the largest non-McNugget number is 43. The fact that any integer larger than 43 is a McNugget number can be seen by considering the following integer partitions
  Any larger integer can be obtained by adding some number of 6s to the appropriate partition above.
  Alternatively, since  and , the solution can also be obtained by applying a formula presented for  earlier:
  Furthermore, a straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as:
  boxes of 6 and 9 alone cannot form 43 as these can only create multiples of 3 (with the exception of 3 itself);
  including a single box of 20 does not help, as the required remainder (23) is also not a multiple of 3; and
  more than one box of 20, complemented with boxes of size 6 or larger, obviously cannot lead to a total of 43 McNuggets.
  Since the introduction of the 4-piece Happy Meal-sized nugget boxes, the largest non-McNugget number is 11. In countries where the 9-piece size is replaced with the 10-piece size, there is no largest non-McNugget number, as any odd number cannot be made.
caption: A box of 20 McDonald's Chicken McNuggets.
exif: {}