CODEWITHSUNDEEP
pythonalgorithmdiophantine
Rafael Adel
Rafael Adel

Reputation: 7759

Solving three variables Diophantine equation in Python

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.

Upvotes: 2

Views: 10547

Answers (9)

Ibrahim zawra
Ibrahim zawra

Reputation: 317

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 +'>')

Upvotes: 0

Stella Yang
Stella Yang

Reputation: 1

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

Upvotes: 0

THaDude
THaDude

Reputation: 1

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

Upvotes: 0

Chinmay Lokesh
Chinmay Lokesh

Reputation: 691

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.

Upvotes: 0

Mohit S Gujarathi
Mohit S Gujarathi

Reputation: 11

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.

Upvotes: 1

Rafe
Rafe

Reputation: 5295

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.

Upvotes: 1

aga
aga

Reputation: 29434

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.

Upvotes: 4

Daniel Fischer
Daniel Fischer

Reputation: 183968

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.

Upvotes: 3

orlp
orlp

Reputation: 117761

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.

Upvotes: 2

Related Questions