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

[John Posner]

On 8/18/2010 1:38 PM, cbrown at cbrownsystems.com wrote:

>>> To go the other way, if d = 1, then there exists integers (not
>>> neccessarily positive) such that
>>
>>> a*x + b*y + c*z = 1

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


 >>> show_gcd(124, 39)
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])