Finding largest number with no Diophantine representation (in Python)

[ephedyn]

Homework Statement

Write an iterative program to find the largest integer n such that the equation

6a + 9b + 20c = n

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

Homework 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.

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.

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!

 

[ephedyn]

Anyone? (:

 

[NascentOxygen]

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:

    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.

 

[uart]

Anyone? (:

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

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 let's you easily test the partial code. It will also make the main body of your program much simpler and easier to understand.