Finding largest number with no Diophantine representation (in Python)

  • Comp Sci
  • Thread starter ephedyn
  • Start date
  • #1
170
1

Homework Statement


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.


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.

Code:
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!
 

Answers and Replies

  • #2
170
1
Anyone? (:
 
  • #3
NascentOxygen
Staff Emeritus
Science Advisor
9,244
1,073
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:
    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.
 
  • #4
uart
Science Advisor
2,797
21
Anyone? (:
How about you start by defining a function "hasSolution(n)" to test if the equation has a suitable solution.
Code:
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.
 

Related Threads on Finding largest number with no Diophantine representation (in Python)

Replies
0
Views
2K
  • Last Post
2
Replies
39
Views
2K
Replies
10
Views
3K
Replies
1
Views
645
Replies
8
Views
727
Replies
1
Views
1K
Replies
4
Views
273
  • Last Post
Replies
4
Views
2K
Replies
7
Views
869
Top