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.
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.
My guess is they forgot to specify , or equivalently, .
I will put the code I wrote in a spoiler box so you can try to guess at an algorithm.
Output:Spoiler:
Edit: This code is rather sloppy, I will rewrite in a little bit.Code:7,3,6 190,139,161 1870,903,1797 Elapsed: 0.132 seconds
You're welcome.
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.)
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.