Sum of Three Cubes (Java)

Imagine being able to describe every number in existence as a sum of three cubes. Now imagine being able to describe only some numbers in existence as a sum of three cubes... find out in this post!



Inspired by a rather recent Numberphile video, I took it upon myself to try and crack some code using Java and maths. Basically, many integers can be written as a sum of three numbers cubed, fitting the form written below. These integers can be positive or negative, as cubing negative numbers results in a negative number still. As you can imagine, the amount of possibilities can become seemingly endless. To my surprise, though, for some integers, even small ones, the solutions were limited to just one triplet, and for others, an infinite amount, such as the number 1. Even further, solutions have been proven impossible for some integers, while others have not even been solved yet like the number 33! Below is also a table (of test cases, incidentally) where you can see some examples of what I mean (you should watch the video, too!).

x	formulae
-10	-4^3 + 3^3 + 3^3
2	0^3 + 1^3 + 1^3
5	No matches!
100	-6^3 + -3^3 + 7^3
...	...

$x=a^3+b^3+c^3$

Because the possibilities are infinite and any integer could be a solution, it is difficult to find a concrete formula for this process. So, we shall brute-force (don't do this). I have written a Java program which, nice and slowly, checks every single integer combination in a range of integers for solutions. Unsurprisingly, the answer for 33 has not come up just yet. It is good to know that there is a formula for numbers that simply do not have a solution. These numbers fit in this form:

$9k\pm 4$

 OR $(x\pm 4) \mod 9 =0$

 SINCE $x^3\equiv -1,0, \text{or } 1 \mod 9$ 

However, there are some key features of Java that I have utilized in the program which I believe improve its clarity immensely, (seemingly at the cost of performance, but we're way past optimized code now...!)

What does CubeSums.java do?

This file includes an object class called Polynomial, a datatype which stores three BigInteger types which accommodate to a, b, and c in the above formula. A comparison method is also implemented in Polynomial, allowing for the program to compare two Polynomial objects for similarity, as duplicates are usually found in different orders of a, b, and c.

Using Polynomial objects, the program then has a method, calculateCubes, whose parameter is the intended sum of the three cubes which are to be found (corresponding to x in the above formula). The method then basically checks every single integer in the range of:  \[[0-CONSTANT, 0+CONSTANT]\]
This constant is predetermined by a final integer declared in CubeSum.

What is a BigInteger?

In Java, BigInteger is a java.math class which allows for HUGE numbers. Note the storage capacities of Java primitive data types below.

datatype	signed range
byte	-(2^7) to (2^7 - 1)
short	-(2^15) to (2^15 - 1)
int	-(2^31) to (2^31 - 1)
long	-(2^63) to (2^63 - 1)
float	-(2^31) to (2^31 - 1)  [32-bit, or ~7 decimal places]
double	-(2^63) to (2^63 - 1)  [64-bit, or ~16 decimal places]
boolean	true or false
char	'\u0000' to '\uffff' 16-bit Unicode, 0 to (2^16 - 1)
BigInteger	really big

Seriously, BigInteger is truly huge. There's no real limit, but generally it could be guessed that the range extends to something like $(2^{32})^{2147483647}$... yeah.

I challenge you to think of formulas for this problem! Though there are papers for methods and processes, it is difficult to crack.