Generating Values For Diophantine Equations in Java?

Question

I have a program to code where it will solve a 5-1 fifth order Diophantine equation which is basically A^5 + B^5 + C^5 + D^5 + E^5 = F^5, where 0 < A <= B <= C <= D <= E <= F <= N. The way I am going to be implementing it is precomputing the values a given N value and then store it into an array. So for instance if N is 100, it will store the values between 1 to 100 in an array.

I will then compute the values of the first group, A^5 + B^5 + C^5, and the second group, F^5 - (D^5 + E^5), and compare the values from the first group to the second to see if they match. If it matches, then a solution is found.

My question is, how would I go about to compute all possible values of the two groups using the array of values between 1 to N? I have the idea down, but coding it out, I am not sure how to approach it. Can anyone please give me some hints? I am not asking for the solution as to how to code it, I just want some tips/hints which can help me understand the coding process a bit better. Thanks!

Answer 1

Better solution, first generate all 5th order values and store them in an array.

Then use 3 nested loops to generate every combination of F^5-E^5-D^5 store all these combinations

Then use 3 different nested loops to generate every combination of A^5+B^5+C^5 and store all these values.

Use 2 nested loops to compare the values of F^5-E^5-D^5 and A^5+B^5+C^5. if they are the same you have a solution. print the corresponding values of a,b,c,d,e and f.

we only use 2 pairs of 3 nested loops. this solution will be O(3nlogn) if not O(3n)

Answer 2

I would definitely start by computing all the 5th order values for every number 1 to N then I would start with the side F^5 - (A^5 + B^5 + C^5 + D^5 + E^5 ),

1)outer loop, generate values for F^5 begin with highest possible values luckily we know that the smallest value of F is 72. Lander and Parkin (1967)

for the remaining loops start with lowest values,

2)second loop, generate values for E^5

3)3rd loop, generate values for D^5, test value for F^5 - (D^5 + E^5) if negative then you can break this loop (but not outer loops

continue with 3 remaining loops for 3 remaining values. If your equation each loop will have less and less values to test. since we can stop whenever the equation becomes negative or we reach numbers that have already been used

any solution where the equation equals zero is a solution.

time analysis is difficult, first 2 loops will result if N^2, but the remaining 4 loops will be much smaller, perhaps even logn time each hopefully nlogn time together

I tested with n=600. which has a largest solution of
218^5 + 276^5 + 385^5 + 409^5 + 495^5 = 553^5 an N^6 equation would arrive at this solution in 4E16 steps, mine reaches it in 2E15 or 5% of the time.

not sure if this would get it down to n^3logn but it gets you much closer by skipping massive amounts of incorrect solutions.

Answer 3

A small improvement over @Gregory solution would be shaving a few values here and there.

1.

I don't see why we should stop when the given equation is negative since we know that each letter is smaller than the previous one. In that case, for example, the first two loops should take around (N^2/2) steps.

2.

In the second cycle (E) we can consider the fact that

F^5 =  A^5 + B^5 + C^5 + D^5 + E^5 < 5*E^5 

therefore in the cycle for E we don't have to start with 0 but we can start with first E where

5*E^5 > F^5

and go up to F-1.

In the third cycle (D) we'd have a similar inequality to the one above

 F^5 - E^5 = A^5 + B^5 + C^5 + D^5 < 4^D5

and we should start testing for the first D that fulfills this condition.

The same applies to the rest of the inner cycles.

This doesn't look like much but the same idea helped in a few competition problems.