I am assisting a programming comp, and our team had a practice question for finding values a,b,c such that:

a^3 - b^3 - c^3 = 100

Currently, we had the idea of doing random number tests which squares, by restricting the possibilities for the numbers based on size and nature (obviously we had to end with an even number, etc). Additionally, we tried doing random testing for a (i.e subbing a value in) and then making the condition b^3 + c^3 = a^3 - 100 to find appropriate b and c values through more testing. However, both methods, as you image, take too long. We have a limit of about 10 seconds so some guessing is possible.

I am really stumped and would appreciate any help.

Let a^3 = 100 and b = 0 and c = 0 and you get 100 - 0 - 0 = 100 so (100^{1/3},0,0) satisfies the equation. What is the exact purpose of this question. Maybe you should write the question in full.

I am assisting a programming comp, and our team had a practice question for finding values a,b,c such that:

a^3 - b^3 - c^3 = 100

Currently, we had the idea of doing random number tests which squares, by restricting the possibilities for the numbers based on size and nature (obviously we had to end with an even number, etc). Additionally, we tried doing random testing for a (i.e subbing a value in) and then making the condition b^3 + c^3 = a^3 - 100 to find appropriate b and c values through more testing. However, both methods, as you image, take too long. We have a limit of about 10 seconds so some guessing is possible.

I am really stumped and would appreciate any help.

Simple brute force gives answer very quickly, the numbers are very small.

The exact problem:
There are only three known solutions to the equation
a^3 – b^3 – c^3 = 100
with positive integer values for a, b and c.
Write a program that can generate all of them systematically and in a reasonable time.
The program must be able to produce the answers without duplicates in less than 10 seconds real
time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
shortcuts that you build into the program must be logically justified, not the result of implementing a
long-running brute-force algorithm and using the results to filter the generator.

let a = 2x^{1/3}, b = a = x^{1/3} and c = x^{1/3}. This gives 8x -x -x = 6x = 100. x = 100/6. Then take the 3rd root of it and you get all three numbers right away.[/ignore]

The exact problem:
There are only three known solutions to the equation
a^3 – b^3 – c^3 = 100
with positive integer values for a, b and c.
Write a program that can generate all of them systematically and in a reasonable time.
The program must be able to produce the answers without duplicates in less than 10 seconds real
time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
shortcuts that you build into the program must be logically justified, not the result of implementing a
long-running brute-force algorithm and using the results to filter the generator.

This is much, much better. You can start off by a brute force triple for loop where you generate each number from 1 to 100 for each of the variables, but obviously this is going to be very inefficient since you will be testing 100^3 = 1,000,000 triplets. However you can definitely explore the symmetry of the question since if you get a solution a,b,c then a,c,b will be a solution also. Since you have only 3 known solutions one of those must have b = c . So you can reduce the equation to a^3 - 2 b^3 = 100 to find that one.

To solve the rest you can assume b and c are different and take it from there.

The exact problem:
There are only three known solutions to the equation
a^3 – b^3 – c^3 = 100
with positive integer values for a, b and c.
Write a program that can generate all of them systematically and in a reasonable time.
The program must be able to produce the answers without duplicates in less than 10 seconds real
time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
shortcuts that you build into the program must be logically justified, not the result of implementing a
long-running brute-force algorithm and using the results to filter the generator.

Kind of hard to help you with a question when we don't know what the question is!

However there is something wrong with the problem. Maybe it means . Because in 1 second on my system, naive brute force gives four solutions

Note that I stopped checking for answers as soon as 3 were found. I also made no attempt to prove that only 3 answers exist. In a sense, I already found twice the number of solutions asked for by the problem anyway..

By the way, I guess you looked at my code. Did you have any questions about it?

Edit: I forgot the problem stated "three known solutions" instead of "three solutions", so maybe proving the number of solutions is difficult, I haven't studied this kind of Diophantine much and wouldn't attempt a proof at present. (And the wording of the question implies it is an open problem.)

Last edited by undefined; August 13th 2010 at 11:40 PM.

Undefined, is your code so fast because it is storing all the values in arrays first and then doing the math with them so that you don't have to do the powers all the time?

Undefined, is your code so fast because it is storing all the values in arrays first and then doing the math with them so that you don't have to do the powers all the time?

Yes, that's the main speedup. ArrayList is the standard growable array in Java, compared with normal arrays which aren't growable (have fixed size). TreeSet has a much faster contains() method than ArrayList, but TreeSet does not have a get() method (you must access the elements through an Iterator which is a little slow), so I used both in coordination.

And the algorithm is just: generate cubes starting from 1 and increasing; if the cube is greater than 100, subtract 100 from it and then subtract cubes from that (stop halfway to ensure ) and see if the result is a cube.