On Aug 16, 1:23 am, Roald de Vries <downa...@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...@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 -- http://mail.python.org/mailman/listinfo/python-list