McDonald's Chicken McNugget Combo Conundrum: Week #53

[Jameson]

At McDonald's you can order Chicken McNuggets in boxes of 6, 9, and 20. What is the largest number of nuggets that it is not possible to obtain by purchasing some combination of boxes?
--------------------

 

[Jameson]

Congratulations to the following members for their correct solutions:

1) Sudharaka

Solution (from Sudharaka):

Spoiler

The largest number is 43. (Refer >>this<<)

This problem stems from the Frobenius Coin Problem. Since there's no explicit formula known to calculate the Frobenius number when the number of elements of a set is three or more, one way to solve this problem is to a numerical method such as the Rödseth's algorithm.

Some additional comments:

Spoiler

As you can see on the Wikipedia page linked above, the complete list of number of Chicken McNuggets you can't make with boxes of 6, 9 and 20 is 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43.

Here's how you can make the numbers 44-49 with 6, 9, and 20.

$$44 = 6 + 9 + 9 + 20$$
$$45 = 9 + 9 + 9 + 9 + 9$$
$$46 = 6 + 20 + 20$$
$$47 = 9 + 9 + 9 + 20$$
$$48 = 6 + 6 + 9 + 9 + 9 + 9$$
$$49 = 9 + 20 + 20$$

You can continue the sequence by adding 6 to the above list so again we see that 43 is the largest number we can't make this way.