looping through possible combinations of McNuggets packs of 6, 9 and 20

[Roald de Vries]

On Aug 12, 2010, at 11:33 AM, Paul Rubin wrote:
> Baba <raoulbia at gmail.com> writes:
>> exercise: given that packs of McNuggets can only be bought in 6, 9 or
>> 20 packs, write an exhaustive search to find the largest number of
>> McNuggets that cannot be bought in exact quantity.
>
> Is that a homework problem?  Hint: first convince yourself that a
> largest number actually exists.

Good point. There is actually an upper bound. Let's take 6 packs of  
20, that's 120 nuggets.
Now 121 nuggets can be reached by substituting 1 pack of 20 with 2  
packs of 6 and 1 pack of 9.
122 = 4*20 + 2*(2*6+9)
123 = 3*20 + 3*(2*6+9)
...
126 = 6*20 + 6
127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
... etcetera.

Now you have to find the largest number below 120, which you can  
easily do with brute force (untested):

can_be_bought = [False for i in range(120)]
for twenties in range(6):
     for nines in range(14):
         for sixes in range(20):
             can_be_bought[twenties*20+nines*9+sixes*6] = True
for i in reverse(range(120)):
     if not can_be_bought[i]: return i

Cheers, Roald