looping through possible combinations of McNuggets packs of 6, 9 and 20
cbrown at cbrownsystems.com
cbrown at cbrownsystems.com
Mon Aug 16 19:28:13 CEST 2010
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
More information about the Python-list
mailing list