1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding largest number with no Diophantine representation (in Python)

  1. Oct 6, 2012 #1
    1. The problem statement, all variables and given/known data
    Write an iterative program to find the largest integer n such that the equation

    [tex]6a + 9b + 20c = n[/tex]

    where a, b, c are nonnegative integers, has no solution.


    2. Relevant equations

    We are given that the set of n in {x, x+1, x+2, ..., x+5} has nonnegative solutions a, b, c to the equation 6a + 9b + 20c = n if and only if it is possible to find solutions for all n ≥ x. In other words, we should loop our program until we have a list of 6 consecutive integer values, and the first member of the previous list of values stored (which fails this test of consecutive integers) is the desired solution.

    We are also given the example that n = 50, 51, 52, 53, 54, 55 have solutions, which is nice, so the program shouldn't need to compute for a very long time.

    3. The attempt at a solution

    I did something like this, with five nested while loops (I truncated the remaining two so you guys don't have to bear with the pain of reading horrible code haha.) The issue I'm facing is that the nested loop will just go on forever. I can't figure the way to make it terminate at the smallest possible increment from solutionSet[5] before going on to the next nested loop and so on. (In the first test case, the nested loops should terminate when they return 9, 12, 15, 18, 21.) The conditional test of the outermost loop is also messed up, because when I get my desired [9,12,15,18,21] as the first set, it will just terminate there.

    Code (Text):

    solutionSet= [1, 2, 3, 4, 5, 6]
    while solutionSet == range(solutionSet[0],solutionSet[5]+1)

        a = 0;
        b = 0;
        c = 0;
        index = 0;
        x = 0;

        while x != solutionSet[5]+1
            cycle = index % 4;
            if cycle == 1
                a = a+1;
            elif cycle == 2
                b = b+1;
            elif cycle == 3
                c = c+1;
            index = index + 1;
            x = 6*a + 9*b + 20*c;
            solutionSet[0] = x;

        a = 0;
        b = 0;
        c = 0;
        index = 0;
        x = 0;

        while x != solutionSet[5]+2
            cycle = index % 4;
            if cycle == 1
                a = a+1;
            elif cycle == 2
                b = b+1;
            elif cycle == 3
                c = c+1;
            index = index + 1;
            x = 6*a + 9*b + 20*c;
            solutionSet[1] = x;

        a = 0;
        b = 0;
        c = 0;
        index = 0;
        x = 0;

        while x != solutionSet[5]+3
            cycle = index % 4;
            if cycle == 1
                a = a+1;
            elif cycle == 2
                b = b+1;
            elif cycle == 3
                c = c+1;
            index = index + 1;
            x = 6*a + 9*b + 20*c;
            solutionSet[2] = x;

        ...
        ...
     
    Any tips?

    Thanks!
     
  2. jcsd
  3. Oct 7, 2012 #2
    Anyone? (:
     
  4. Oct 7, 2012 #3

    NascentOxygen

    User Avatar

    Staff: Mentor

    There is only one way to author a good program, and that's to write it in small manageable parts, testing each to confirm it will do what you intend, before combining into something larger.

    First, let me say I don't exactly follow what the goal of the final program is, but let's look at a snippet of your code:
    Code (Text):
        while x != solutionSet[5]+1
            cycle = index % 4;
            if cycle == 1
                a = a+1;
            elif cycle == 2
                b = b+1;
            elif cycle == 3
                c = c+1;
            index = index + 1;
            x = 6*a + 9*b + 20*c;
            solutionSet[0] = x;
    On the first transit through this, nothing is incremented except "index", so the value of x is set to 0, and solutionSet[0] is also set to 0.
    On the second loop through, "a" becomes 1, so x jumps up to 6.
    On the third loop, "b" is incremented, making x jump to 15, and so on.
    Are you expecting that sooner or later x will become equal to 7? Because if it doesn't, then it is going to miss the exit condition and this "while loop" will never terminate.
     
  5. Oct 8, 2012 #4

    uart

    User Avatar
    Science Advisor

    How about you start by defining a function "hasSolution(n)" to test if the equation has a suitable solution.
    Code (Text):

    def hasSolution(n) :
    # Brute force search for non-negative integer solution to 6a + 9b +20c = n
    # Takes integer. Returns boolean.
        ....
        return ....   # True or False
     
    This "divide and conquer" approach of writing the important elements of your task as functions lets you easily test the partial code. It will also make the main body of your program much simpler and easier to understand.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding largest number with no Diophantine representation (in Python)
Loading...