Conditional number problem

• August 13th 2010, 10:03 PM
corndog
Conditional number problem
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.
• August 13th 2010, 10:09 PM
Vlasev
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.
• August 13th 2010, 10:11 PM
corndog
a,b,c are defined as positive non zero integers.
• August 13th 2010, 10:13 PM
undefined
Quote:

Originally Posted by corndog
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.
• August 13th 2010, 10:16 PM
corndog
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.
• August 13th 2010, 10:17 PM
Vlasev
[ignore]Here's another thing

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]

I just realized you are talking about integers!
• August 13th 2010, 10:21 PM
Vlasev
Quote:

Originally Posted by corndog
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.
• August 13th 2010, 10:26 PM
undefined
Quote:

Originally Posted by corndog
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 $b \ge c$. Because in 1 second on my system, naive brute force gives four solutions

(7,6,3)
(7,3,6)
(190,161,139)
(190,139,161)
• August 13th 2010, 10:27 PM
corndog
Perhaps it's a typo in the question?
• August 13th 2010, 10:58 PM
undefined
Quote:

Originally Posted by corndog
Perhaps it's a typo in the question?

My guess is they forgot to specify $b \ge c$, or equivalently, $b \le c$.

I will put the code I wrote in a spoiler box so you can try to guess at an algorithm.

Spoiler:

Code:

```import java.util.ArrayList; import java.util.TreeSet; public class CubeMinus100Sum2Cubes {     static ArrayList<Long> cubes = new ArrayList<Long>();     static TreeSet<Long> cubes2 = new TreeSet<Long>();         public static void main(String[] args) {         long c, c2, c3, t=time();         int i, j, lim = 2000, count=0; // limit chosen arbitrarily (guess)         for(c=1; c<lim+1; c++) {             c2=c*c*c;             cubes.add(c2);             cubes2.add(c2);         }         outer:         for(i=4; i < lim; i++) {             c=cubes.get(i)-100;             for(j=0, c2=cubes.get(j); c2 <= c/2; j++, c2=cubes.get(j)) {                 if (cubes2.contains(c-c2)) {                     c2 = Math.round(Math.pow(c-c2,(1/3.0)));                     System.out.println(i+1+","+(j+1)+","+c2);                     if (++count == 3)                         break outer;                 }             }         }         System.out.println("Elapsed: "+(time()-t)/1000.0+" seconds");     }         static long time() {         return System.currentTimeMillis();     } }```
Output:
Code:

```7,3,6 190,139,161 1870,903,1797 Elapsed: 0.132 seconds```
Edit: This code is rather sloppy, I will rewrite in a little bit.
• August 13th 2010, 11:14 PM
undefined
Quote:

Originally Posted by undefined
Edit: This code is rather sloppy, I will rewrite in a little bit.

Hmm, my sloppier code runs faster. Go figure.

Spoiler:

Code:

```import java.util.ArrayList; import java.util.TreeSet; public class CubeMinus100Sum2Cubes {     static ArrayList<Long> cubes = new ArrayList<Long>();     static TreeSet<Long> cubes2 = new TreeSet<Long>();         public static void main(String[] args) {         long c, c2, i, t=time();         int j, count=0;         outer:         for(i=1, c=1;; i++, c=i*i*i) {             cubes.add(c);             cubes2.add(c);             c-=100;             if(i > 4)             for(j=0, c2=1; c2 <= c/2; j++, c2=cubes.get(j)) {                 if(cubes2.contains(c-c2)) {                     c2 = Math.round(Math.pow(c-c2,(1/3.0)));                     System.out.println(i+","+(j+1)+","+c2);                     if(++count == 3)                         break outer;                 }             }         }         System.out.println("Elapsed: "+(time()-t)/1000.0+" seconds");     }         static long time() {         return System.currentTimeMillis();     } }```
Output:
Code:

```7,3,6 190,139,161 1870,903,1797 Elapsed: 0.165 seconds```
• August 13th 2010, 11:24 PM
corndog
Thank you very much for your assistance.
• August 13th 2010, 11:28 PM
undefined
Quote:

Originally Posted by corndog
Thank you very much for your assistance.

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.)
• August 14th 2010, 01:23 AM
Vlasev
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?
• August 14th 2010, 07:06 AM
undefined
Quote:

Originally Posted by Vlasev
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 $b\le c$) and see if the result is a cube.