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.

 

[LudusRex]

I would first commend you for attempting to solve this problem and for recognizing the need to optimize your code. However, I would also recommend approaching this problem in a more organized and efficient manner.

First, it is important to understand the problem and what it is asking for. In this case, we are looking for the largest integer n that has no solution to the given Diophantine equation. This means that we do not need to iterate through all possible values of n, but rather we can start from the largest value and work our way down until we find the desired solution.

Next, I would suggest using a single loop instead of multiple nested loops. This will make the code more readable and easier to debug. Within this loop, you can check if the current value of n satisfies the Diophantine equation by using a simple modulo operation. If it does, then you can break out of the loop and move on to the next value of n. If it doesn't, then you have found the desired solution and can break out of the loop.

In terms of optimization, you can also use the fact that the equation has a pattern in its solutions. For example, for every 6 consecutive values of n, you only need to check the first and last values to determine if there is a solution. This can save a lot of computation time.

Overall, my advice would be to approach this problem in a more organized and systematic way, and to use the patterns and properties of the equation to optimize your code. Good luck!