Solving three variables Diophantine equation in Python

Question

I'm a beginner in Python, and tried to take MIT 6.00, the page provided is the assignments page.

I'm at assignment 2, where i have to find a solution for Diophantine equation, i'm really not that great in math, so i tried to understand what it does as much as i can, and think of a solution for it.

Here's what i got to :

def test(x):
    for a in range(1,150):
        for b in range(1,150):
            for c in range(1,150):
                y = 6*a+9*b+20*c
                if y == x:
                    print "this --> " , a, b, c
                    break
                else : ##this to see how close i was to the number
                    if y - x < 3: 
                        print a, b, c , y

The assignment states that there's a solution for 50, 51, 52, 53, 54, and 55, but unfortunately the script only gets the solution for 50, 53 and 55.

I'd be very grateful if someone explained what's wrong in my code, or if i'm not understanding Diophantine equation at all, please tell me what is it all about and how to find a solution for it, since i cant get the assignment's explanation into my head.

Thanks.

Answer 1

The assignment says:

To determine if it is possible to buy exactly n McNuggets, one has to solve a Diophantine equation: find non-negative integer values of a, b, and c, such that 6a + 9b + 20c = n.

It seems that you have to include zero in the ranges of your function. That way, you can find solutions for all the numbers you need.

Answer 2

A solution to

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

with integers a, b, c must have at least one of the integers 0 or negative. Some solutions are

6*7 + 9*1 + 20*0 = 51
6*0 + 9*(-1) + 20*3 = 51

Depending on the constraints in the assignment, you need to include 0 or even negative numbers among the possible coefficients.

Answer 3

A solution for 51 is 5*9 + 1*6.

Hint: where's the 20? What does this mean for it's coefficient?

A solution for 54 is 3*20 + (-1)*6. You figure out the rest.

Answer 4

For a start, you can usefully exploit bounds analysis. Given

6a + 9b + 20c = n
0 <= a
0 <= b
0 <= c

we can systematically set pairs of {a, b, c} to 0 to infer the upper bound for the remaining variable. This gives us

a <= floor(n / 6)
b <= floor(n / 9)
c <= floor(n / 20)

Moreover, if you pick a strategy (e.g., assign c then b then a), you can tighten the upper bounds further, for instance:

b <= floor((n - 20c) / 9)

Also, the last variable to be assigned must be a function of the other variables: you don't need to search for that.

Answer 5

You can start your range for a,b,c from 0 to 150.

Actually even I am a beginner and have started out from MIt 6.00 only. ON reading their problem ,I think 150 it the limit to the largest number which cannot be possible to take.

Answer 6

This is a solution in Perl. rather a hack by using Regex.

Following this blog post to solve algebraic equations using regex.

we can use the following script for 3x + 2y + 5z = 40

#!/usr/bin/perl
$_ = 'o' x 40;
$a = 'o' x 3;
$b = 'o' x 2;
$c = 'o' x 5;
$_ =~ /^((?:$a)+)((?:$b)+)((?:$c)+)$/;
print "x = ", length($1)/length($a), "\n";
print "y = ", length($2)/length($b), "\n";
print "z = ", length($3)/length($c), "\n";

output: x=11, y = 1, z = 1

the famous Oldest plays the piano puzzle ends up as a 3 variable equation

This method applies for a condition that the variables are actually positive and the constant is positive.

Answer 7

Check this one I adapted from yours. It seems to fixed your problem:

variables=range(0,10)
exams=range(51,56)
for total in exams:
    for a in variables:
        for b in variables:
            for c in variables:
                if total==4*a+6*b+20*c:
                    print a, 'four pieces', b, 'six pieces','and', c ,'twenty pieces', 'for a total of', total

Answer 8

The break function will only break out of the closest loop. The code below uses an indicator to break out of each loop.

    n = 1     # n starting from 1
    count = 0 # Count + 1 everytime we find a possible value. 
              # Reset = 0 after a non-possible value. 
    notPossibleValue = ()
    while True:
        ind = 0 # become 1 if int solutions were found
        for c in range (0,n/20+1):
            if ind == 1: break 
            for b in range (0,n/9+1):
                if ind == 1: break 
                for a in range (0, n/6+1):
                    if (n-20*c) == (b*9+a*6):
                        count += 1
                        ind = 1                    
                        # print 'n=', n, a,b,c, 'count', count                       
                        break # Break out of "a" loop
        if ind == 0:
            count = 0
            notPossibleValue += (n,)
            # print notPossibleValue, 'count', count
        if count == 6:
            print 'The largest number of McNuggets that cannot be bought in exact quantity is', notPossibleValue[-1]
            break
        n += 1

Answer 9

n=1
a=0
b=0
c=0
mcnugget = []
for i in range (n,100):
   for a in range (0,20):
       if  6*a + 9* b +20*c ==i:
           mcnugget.append(i)
           break
       else:
            for b in range (0,12):
                if  6*a + 9* b +20*c ==i:
                    mcnugget.append(i)
                    break
                else:
                    for c in range(0,5):
                        if  6*a + 9* b +20*c ==i:
                            mcnugget.append(i)
                            break
   else:
        if i>8:
            if mcnugget[-1]==mcnugget[-2]+1==mcnugget[-3]+2==mcnugget[-4]+3==mcnugget[-5]+4==mcnugget[-6]+5 and mcnugget[-6]>0 :
                break

mcnugget = set (mcnugget)
mcnugget = list (mcnugget)
count = 0
for z in mcnugget:
   count += 1
   if mcnugget [count]==mcnugget [count-1]+1==mcnugget [count-2]+2==mcnugget [count-3]+3==mcnugget [count-4]+4==mcnugget[count-5]+5:
      biggestN= mcnugget[count-6]
      break
#print (mcnugget)
biggestN = str(biggestN)

print ('Largest number of McNuggets that cannot be bought in exact quantity: <'+ biggestN +'>')