McNugget numbers

McNugget numbers – The Answer

Last Sunday I posted a question I had asked my self about McNugget numbers with a promise that I would actually post an answer to the problem as well. So here we go.

McNuggetsThe McNugget numbers are fairly well described on the Internet and both Wolfram and WikiPedia describes the problem.

McNugget numbers with 4,6,9 and 20

I used a brute force approach to solving the first problem; What are the McNugget numbers you can make with 4,6,9 and 20 McNugget boxes? My stopping condition was “I have to find four consecutive numbers based on combinations of McNugget boxes. Then I can make an arbitrary larger number by adding 4-boxes to one of these four numbers. That proves the existence of any other number as a linear combination of McNugget boxes for this case. There might be a cheaper way to make the same number though.

Anyway the list as I made it out is

Number McNugget boxes
1
2
3
4 4
5
6 6
7
8 4+4
9 9
10 6+4
11
12 6+6
13 9+4
14 6+4+4
15 9+6

From thereon I can make any number with 12-15 + n*4.

11 is called the Frobenious number of {4,6,9,20}  since it is the largest number you can’t make as a linear combination of the set.

McNugget numbers with 6,9 and 20

If we remove the 4-box and just consider the numbers 6,9 and 20 the answer is higher and at least for me it was more challenging to solve in my head. Once again, I took the approach that ones we have 6 consecutive numbers we can make any number larger than that.

The complete list of McNugget numbers are 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43 and after that we have

Number McNugget boxes
44 20+4*6
45 5*9
46 2*20+6
47 20+3*9
48 8*6
49 2*20+9

Which means we can now make any higher number based on these 6 numbers and a multiple of 6.

The existence of a highest McNugget Number

In the previous sections the proof that we could make any higher number based on the size of McNugget boxes was based on the assumption that I could find 4 or 6 consecutive number which I could describe. And I could….

However, in more general terms this is know as Schur’s Theorem which states

That for a set of coprime numbers (meaning that the greatest common divisor for the set is 1) there exists a value x such that any value larger than x can be expressed as a linear integer combination of the set.

The opposite example is a set of non coprime numbers such as {2,4,6} which are not coprime as gcd(2,4,6) = 2. In this case you wont be able to express any odd numbers through a combination of the given set and thus there exist no highest number which cannot be expressed.

If you want to see how many different combinations of McNugget boxes can give a certain number the Dynamic programming algorithm derived in Problem 31 of Project Euler can be modified to give you the result.

Happy snacking.

Posted by Kristian

2 comments

Nice one. This was really fun. I like your stopping condition (get 6 consecutive numbers), I didn’t think of that.
One thing that makes me sad is that I was the only one who posted on “The Question” article. You really deserve more comments on this blog… Really awesome and well written articles. Well.. Keep up the good work!

Thanks for the kind comment, I am glad you enjoyed it 🙂

I hope to grow the blog and attract more visitors, but as far as I can see now it takes lot of time and hard work. But I enjoy it and I will just keep on working on it.

/Kristian

Leave a Reply