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

[cbrown at cbrownsystems.com]

On Aug 17, 2:44 pm, Baba <raoul... at gmail.com> wrote:
> On Aug 16, 6:28 pm, "cbr... at cbrownsystems.com"
>
> <cbr... at cbrownsystems.com> wrote:
> > 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?

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.

>
> > 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?
>

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