looping through possible combinations of McNuggets packs of 6,9 and20

[Giacomo Boffi]

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 need at least an odd number in your set, because summing even
numbers only you'll never get an odd result

 

[Baba]

well i still believe that the key is the smallest sized pack and
there's no need to go into higher mathematics to solve this problem.
I think below code works within the limits of the exercise which
states to look at a maximum range of 200 in order not to search
forever.

packages=[2,103,105]
min_size=min(packages[0],packages[1],packages[2])
cbc=0 #cbc=can_buy counter
for n_nuggets in range(1,200):
if cbc>=min_size:
break
can_buy=False
for a in range (n_nuggets/packages[0]+1):
for b in range (n_nuggets/packages[1]+1):
for c in range (n_nuggets/packages[2]+1):
#print "trying for %d: %d %d %d" % (n_nuggets,a,b,c)
if packages[0]*a+packages[1]*b+packages[2]*c==n_nuggets:
can_buy=True
break
if can_buy==True:
cbc+=1
else:
cbc=0
sol=n_nuggets
print sol



Baba

 

[John Posner]

packages=[2,103,105]
min_size=min(packages[0],packages[1],packages[2])

or:

min_size = min(packages)

-John

 

[cbrown]

Hi Chas, Roald,

These are all complicated formula that i believe are not expected at
this level. If you look at the source (see my first submission) you
will see that this exercise is only the second in a series called
"Introduction to Programming". Therefore i am convinced that there is
a much simpler solution.

The question I was responding to (a different one than your original
question) was whether there was a proof of Baba's conjecture that a
largest unobtainable quantity was possible if, and only if, the three
numbers in question had a gcd of 1. Roald had something like a "gut
feeling" that it was true, but such things are generally much more
clear cut than "gut feelings" - they can often easily be /proven/ to
be true or false, given the right mental tools.

In this case, that proof I gave doesn't immediately yield a concrete
answer to your /original/ question - assuming that a largest
obtainable solution is possible, /how/ do we find the largest
unobtainable solution? But it certainly identifies the conditions
whereby we can easily and quickly say that there is no such solution,
or conversely that such a solution must exist; and that is often
extremely helpful to finding an algorithm that /does/ answer your
original question.

(One thing it does provide is an upper bound to the space of solutions
that you should be looking at - and finding upper bounds and lower
bounds is a common programming task. Again, this isn't something that
you might be "expected" to know about at your level of study, but it
doesn't hurt you to be aware of it either !)

Now, i believe that the number of consecutive passes required to make
this work is equal to the smallest number of pack sizes.

That is your belief, your intuition; and developing good intuitions is
good... BUT...

So if we have
packs of (9,12,21) the number of passes needed would be 9 and...

.... and now whatever you might go on to add is simply "going off into
the weeds", because I have just proven that there can be /no/ such
solution in that case: all three of those numbers are divisible by 3,
so you are not "on the trail" when trying to figure out a general
solution by considering examples of the type you mention.

At your level of study, such things may seem overly complicated (and
are certainly /not/ required to simply answer the question as
originally stated). But consider the thread in this group called
"python interview questions":

http://groups.google.com/group/comp.lang.python/browse_frm/thread/bb4d3514e9842f9e#

The "FizzBuzz" question involves a similar very basic grasp of the
type of mathematical reasoning and thinking that is most valued in
programmers in the job market. Of course, your Python class is not the
right place to be focusing exclusively on this sort of mathematics,
but I would encourage you to simultaneously educate yourself both in
the /language/ learning of Python (which is what your class is largely
about), along with the more universally applicable skill set that
comes from understanding the mathematical justifications of a "good"
algorithm

That additional knowledge will serve you equally well whether you are
programming in Python, Perl, Ruby, Java, C++, D, F, R, and so on
(surely someone will claim "Z" as a language soon, if they haven't
already...).

... the
theorem would read

"If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to
buy any number of nuggets >= 9 given that they come in packs of
9,12,21"

So I would ask as a simple exercise: how would you go about /proving/
that your assertion is actually a /theorem/, and not just a pretty
solid hunch that your statement is true because for small enough
numbers you can easily "do it in your head"? Yes, it's "clearly true",
but that is not a proof! That is the muscle which is exercised by
mathematical reasoning.

However i turn in circles because i don't seem to get any results for
some random pack combinations like (9,12,21) or (10,20,30).

Well, your intuitions are certainly close to the mark. But if you
added to your study a course on discrete mathematics, then you would
also immediately see why such turning in circles obviously can bear no
fruit, and that would give you a great advantage in solving far more
difficult and yet common problems of this type.

Cheers - Chas

 

[Giacomo Boffi]

Is that a homework problem?

yes, and no

it was a homework problem, assigned in 2008, as clearly stated by the OP

most of what was discussed on the ng was clearly stated in the
introduction to the actual problem, so that we can thank Baba for NOT
having read the text of the assignment, leavin' us a couple of days of
amusing and interesting posts

 

[Baba]

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:

could you explain the notation?

what is the difference btw x and x' ?

what is x = d*x', y supposed to say?

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

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

what's the link with 6*a+9*b+20*c=n except the similarity?



furthermore i came across this:

For k = 3, efficient algorithms
have been given by Greenberg and Davison ; if x1 < x2 < x3, these
algorithms run in
time bounded by a polynomial in log x3. Kannan gave a very
complicated algorithm
that runs in polynomial time in log xk if k is fixed, but is wildly
exponential in k. However,
Ram´ırez Alfons´ın proved that the general problem is NP-hard, under
Turing reductions,
by reducing from the integer knapsack problem. So it seems very likely
that there is no
simple formula for computing g(x1, x2, . . . , xk) for arbitrary k.

source: http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf


i would be interested in the answer to problem 3: explain in English
why the theorem is true

@Giacomo: when you say that i have not read the text of the assignment
i tend to disagree. Therefore could you point out what it is i
overlooked that should help me prove my assumption for the
generalisation? Enjoy the sausages btw

tnx
Baba

 

[News123]

could you explain the notation?

what is the difference btw x and x' ?

what is x = d*x', y supposed to say?

gcd(x,y,z) determines the greates number by which all three numbers can
be devided.

2,4,6 for example are all divided by 2
thus d=2
now you dived x,y,z by d and call them x' , y' , z'

The point is if
x,y,z have a gcd grater than one, then you know for sure,
that you will never be able to find the a finit greates amount, which
cannot be bought


if xmymz are all divisible by d, then any combination will also be
dividible by d


thas any number not dividible by d ( for d > 1)

for example n*d + 1

can not be bought

 

[cbrown]

   could you explain the notation?

   what is the difference btw x and x' ?

   what is x = d*x', y supposed to say?

x', y', z' are names for three natural numbers; I could have chosen r,
s, t. "x=d*x'" above simply notes that since x is divisible by d, it
can be written as the product of d and some other natural number, and
the same is true for both y and z. therefore sums of multiples of x, y
and z are always divisible by d.

   what's the link with 6*a+9*b+20*c=n except the similarity?

The link is that it shows that if we have some u, v, and w with

6*u + 9*v + 20*w = n,

and we can find some a, b, and c which satisfy

6*a + 9*b + 20*c = 1

then if we let r = u + a, s = v + b, and t = w + c, we get that

6*r + 9*s + 20*t = n+1

although r, s, and t are not neccessarily positive numbers (as they
must be to solve your original problem). However, if u, v, and w are
sufficiently large compared to a, b, and c, then r, s and t WILL all
be positive.

But we can only find such an a,b, and c because the gcd of 6, 9, and
20 is equal to 1; that is why you can't solve this problem for nugget
pack sizes 6, 12, and 21.

Note that if there is one solution (a,b,c) to the gcd equation, there
infinitely many tuples (a,b,c) which satisfy the gcd equation, for
example:

6*0 + 9*9 + 20*(-4) = 1
6*(-5) + 9*(-1) + 20*2 = 1
6*2 + 9*1 + 20*(-1) = 1

So the proof I gave regarded the /existence/ of a largest
unobtainable, not an algorithm for obtaining one. However from the
last of those three examples, we can see (details are in my original
proof) that the largest unobtainable must be less than

6*0 + 9*0 + 20*(1*5) = 100

so it is potentially helpful for finding an upper bound to the
problem.

furthermore i came across this:

For k = 3, efficient algorithms
have been given by Greenberg and Davison ; if x1 < x2 < x3, these
algorithms run in
time bounded by a polynomial in log x3. Kannan  gave a very
complicated algorithm
that runs in polynomial time in log xk if k is fixed, but is wildly
exponential in k. However,
Ram´ırez Alfons´ın proved that the general problem is NP-hard, under
Turing reductions,
by reducing from the integer knapsack problem. So it seems very likely
that there is no
simple formula for computing g(x1, x2, . . . , xk) for arbitrary k.

source:http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf

i would be interested in the answer to problem 3: explain in English
why the theorem is true

I haven't looked at the link; but to be honest it's unlikely you would
understand it if you are having trouble with the much simpler question
regarding solutions in the case of 6, 12, and 21.

Cheers - Chas

 

[Baba]

Hi Chas

Thanks for that and i agree on your last remark

re the number of required consecutive passes required:

The number of required consecutive passes is equal to the smallest
number because after that you can get any amount of nuggets by just
adding the smallest nugget pack to some other number.

This is only true if gcd(a,b,c)=1.

Thanks to all for the help in getting to the bottom of the exercise. I
have truly enjoyed this and most importantly i have learned some new
things. Hadn't really done any mathematics in a long time and only
starting programming so this was good to get up to speed.

kind regards to everyone!
Baba

 

[cbrown]

Hi Chas

Thanks for that and i agree on your last remark

re the number of required consecutive passes required:

The number of required consecutive passes is equal to the smallest
number because after that you can get any amount of nuggets by just
adding the smallest nugget pack to some other number.

This is only true if gcd(a,b,c)=1.

Thanks to all for the help in getting to the bottom of the exercise. I
have truly enjoyed this and most importantly i have learned some new
things. Hadn't really done any mathematics in a long time and only
starting programming so this was good to get up to speed.

kind regards to everyone!
Baba

Happy to be of service!

Cheers - Chas

 

[John Posner]

That fact is non-trivial, although the proof isn't *too* hard [1]. I
found it interesting to demonstrate the simpler case (a*x + b*y = 1) by
"instrumenting" the classic Python implementation of Euclid's Algorithm:

def show_gcd(a,b):
"""
find GCD of two integers, showing intermediate steps
in both remainder and linear-combination forms
"""
while b:
if a%b > 0:
rem_form = "%d == %d*(%d), rem %d" % (a, b, a/b, a%b)
equ_form = "%d == %d*(1) + %d*(-%d)" % (a%b, a, b, a/b)
print "%3d %3d %-30s %s" % (a,b, rem_form, equ_form)
a,b = b, a%b
print "\nGCD is", a

124 39 124 == 39*(3), rem 7 7 == 124*(1) + 39*(-3)
39 7 39 == 7*(5), rem 4 4 == 39*(1) + 7*(-5)
7 4 7 == 4*(1), rem 3 3 == 7*(1) + 4*(-1)
4 3 4 == 3*(1), rem 1 1 == 4*(1) + 3*(-1)


Performing successive substitutions, bottom to top, using the equations
in the right-hand column:

1 == 4*(1) + 3*(-1)

== 4*(1) + (7*(1) + 4*(-1))*(-1)

== 4*(2) + 7*(-1)

== (39*(1) + 7*(-5))*(2) + 7*(-1)

== 39*(2) + 7*(-11)

== 39*(2) + (124*(1) + 39*(-3))*(-11)

== 39*(35) + 124*(-11)

What could be simpler!

-John


[1] http://math453fall2008.wikidot.com/lecture-3 ("GCD as a linear
combonation" [sic])

 

[cbrown]

That fact is non-trivial, although the proof isn't *too* hard [1]. I
found it interesting to demonstrate the simpler case (a*x + b*y = 1)...

And to get the more general case, if we write (a,b) for gcd of and b,
we can think of the "," as a binary operator that you can show is
associative:

((a,b), c) = (a, (b,c)) = (a, b, c)

and so a proof that exists x,y with a*x + b*y = (a,b) can then be
extended to a proof for an arbitrary number of elements.

(Oddly, "," is also distributive over itself: ((a,b), c) = ((a,c),
(b,c))...)

Cheers - Chas