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

[cbrown at cbrownsystems.com]

On Aug 16, 1:23 am, Roald de Vries <downa... at gmail.com> wrote:
> On Aug 15, 2010, at 11:51 PM, Ian Kelly wrote:
>
>
>
> > On Sun, Aug 15, 2010 at 4:36 PM, Baba <raoul... 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.
>

But 2 is coprime to 7. I think a better counterexample is 6, 10, 15;
no two are coprime, but there is 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"
>

It's easy to prove that there is a largest unpurchasble quantity iff
gcd(x,y,z) = 1.

First, suppose d = gcd(x, y, z); then for some x', y', z' we have that
x = d*x', y = d*y', z = d*z'; and so for any a, b, c:

a*x + b*y + c*z = a*d*x' + b*d*y' + c*d*z'
                = d*(a*x' + b*y' + c*z')

which means that d must always divide the total number of nuggets
purchasable; thus if d >1, there is no largest unpurchasable quantity
(you cannot purchase n*d + 1 nuggets for any n).

To go the other way, if d = 1, then there exists integers (not
neccessarily positive) such that

a*x + b*y + c*z = 1

so therefore

(a*x)*x + (b*x)*y + (c*x)*z = x

Choose A, B, and C to be positive integers with

A + a*x >= 0
B + b*x >= 0
C + c*x >= 0

Then we get a sequence of x consecutive numbers, all purchasable, via

(A + i*a)*x + (B + i*b)*x + (C + i*c)*z
    = (Ax + By + Cz) + i*(ax + by cz)
    = (Ax + By + Cz) + i

with i in range(x).

The next consecutive number is then achieved via

(Ax + By + Cz) + x = (A+1)x + By + Cz

and so on.

Cheers - Chas