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

[cbrown at cbrownsystems.com]

On Aug 16, 11:04 am, Baba <raoul... at gmail.com> wrote:
> 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