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

[Roald de Vries]

On Aug 15, 2010, at 11:51 PM, Ian Kelly wrote:
> On Sun, Aug 15, 2010 at 4:36 PM, Baba <raoulbia at gmail.com> wrote:
>> Hi Mel,
>>
>> indeed i thought of generalising the theorem as follows:
>> If it is possible to buy n, n+1,…, n+(x-1) sets of McNuggets, for  
>> some
>> x, then it is possible to buy any number of McNuggets >= x, given  
>> that
>> McNuggets come in x, y and z packs.
>>
>> so with diophantine_nuggets(7,10,21) i would need 7 passes
>> result:53
>>
>> but with (10,20,30) and 10 passes i get no result
>
> You're on the right track.  In the case of (10,20,30) there is no
> largest exactly purchasable quantity.  Any quantity that does not end
> with a 0 will not be exactly purchasable.
>
> I suspect that there exists a largest unpurchasable quantity iff at
> least two of the pack quantities are relatively prime, but I have made
> no attempt to prove this.

That for sure is not correct; packs of 2, 4 and 7 do have a largest  
unpurchasable quantity.

I'm pretty sure that if there's no common divisor for all three (or  
more) packages (except one), there is a largest unpurchasable  
quantity. That is: ∀ i>1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x| 
y) means "x is no divider of y"

Cheers, Roald