Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question

5 Answers

up vote 3 down vote accepted

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.

share|improve this answer
up vote 3 down vote

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.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
up vote 0 down vote

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.

share|improve this answer
up vote 0 down vote

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.

share

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.