## McNugget Math

Category : Uncategorized

There’s a brainteaser that goes:

McNuggets come in packages of 6, 9 or 20 pieces. So you can easily make any multiple of 6, for example, but you can’t make exactly 7 or 8. You can combine any number of packages, so you can make 6 + 9 + 9 + 20 = 44. What’s the highest number you can’t make (exactly) out of a combination of McNugget packages?

So we know we can make 20, and 21 = 6 + 6 + 9. But we can’t make 22. Or 23. We could keep going, finding which numbers are possible and which ones aren’t. How do we know there’s a maximum “impossible” number? Once we can make a certain number of “possibles” in a row, we can assume we can make any number above that. Do you know what that is?

It’s a pretty decent brainteaser but there’s no nice algebraic way to put the numbers into an equation and spit out the answer. It might seem unsatisfying to a student used to algebra and equations. But it’s a great programming exercise!

### Python to the Rescue!

I wrote a Python program to go through every possible combination of packages (6, 9 and 20) up to the number we’re investigating. If the combination comes out to be exactly 23, for example, it prints out the combination that works. Otherwise it returns an empty list.

```
def nuggets(num):
'''returns the combination [i,j,k]
of nuggets to equal num'''
solution = [] #empty list
# i represents the number of 6-nugget packages
for i in range(int(num/6)+1):
# j represents the number of 9-nugget packages
for j in range(int(num/9)+1):
# k is the 20 nugget packages
for k in range(int(num/20)+1):
# if they combine to make "num"
if 6*i+9*j+20*k == num:
#add that combo to the solution list
solution.append([i,j,k])
return solution
```

The solution for 23 and 24 are shown:

```
>>> nuggets(23)
[]
>>> nuggets(24)
[[1, 2, 0], [4, 0, 0]]
>>>
```

This means there’s no solution for 23, but you can make 24 in two different ways: 1 x 6 + 2 x 9 = 24 and 4 x 6 = 24. I put the numbers in a loop and went up a few dozen to see if they ended:

```
>>> for i in range(25,50):
print(i,nuggets(i))
...
43 []
44 [[1, 2, 1], [4, 0, 1]]
45 [[0, 5, 0], [3, 3, 0], [6, 1, 0]]
46 [[1, 0, 2]]
47 [[0, 3, 1], [3, 1, 1]]
48 [[2, 4, 0], [5, 2, 0], [8, 0, 0]]
49 [[0, 1, 2]]
```

So there’s no way to make 43, but you can make 44 through 49. Do we need to go any higher? Obviously if you can make 44, then you can add a 6-nugget package and make 50. Same with 45. You know you can make 51 by adding a 6. And so on all the way up. The highest number you can’t make is 43.