Discrete Mathematics
Discrete calculations should not be done using floating-point math. You should be suspicious of any results contaminated by floating-point math. The way to compute the cube of an integer is n * n * n. For larger powers, do repeated squaring, or use BigInteger.pow() (which is slower, but immune to overflow).
Variable Usage
To be honest, I found your code extremely difficult to read, mainly due to the way you misuse variables.
- Scope: You should declare and define variables as close as possible to the point of use. If a variable only applies within a loop, declare and define it inside the loop. If it's local to a function, define it as a local variable in the function. Instead, you've used a lot of instance variables, which, for all practical purposes, are "global" (since you only have one class). As you really only have one function, all of the variables should have been local!
- Proliferation: You've declared 19 instance variables. Surely fewer variables would suffice? A human brain can keep track of about 7 items at a time. You have
cSum (an int), cubeSum (an Integer), and cs (a double) — which raises the question, how are they related? (Answer: cSum is never used, and cs is just a temporary variable that shouldn't have been needed at all.) Also, answer and iterations are never used. You've got so many variables that you couldn't keep track of the dead ones to prune. - Cryptic naming: Without studying the code, can you remember what
x, y, k, X, Y, K, J, and floor mean? If not, then your variables are named too cryptically. - Unconventional naming: By connotation, I would expect
x to represent a floating-point number, not a list of Integers. Then, you've also got X, which is a boxed version of j. - Misuse for flow control: To terminate the loop, why do you set a variable and test for
found != true elsewhere? Just return after printing the result — you're done!
Language Disfluency
If you familiarize yourself with the Java language a bit more, you can express yourself less clumsily.
- Prefer primitives: You should always prefer the primitives (e.g.
int) to their boxed counterparts (Integer). Code written using primitives reads better and performs better. The boxed types exist mainly so that you can store them in collections such as ArrayList<Integer>. Even then, the compiler will automatically box and unbox the values for you, so you don't have to say new Integer(n). - Type Promotion: The compiler will automatically perform widening conversions, such as promoting
int to double, so casting is unnecessary in those cases. - Integer division: When dividing an integer by an integer, the result will also be integral (with truncation towards 0). When you do
(int)Math.floor(i/2), you're just promoting i / 2 to a double argument, rounding it to the same double, and casting the result back to an int. It would have been sufficient to just do i / 2.
Time Out… Let's Rewrite!
Let's rewrite the code using the trivial simplifications mentioned so far.
import java.util.ArrayList; public class Cubes { public static void main(String[] args) { new Cubes().find(); } private void find() { ArrayList<Integer> sum = new ArrayList<Integer>(); ArrayList<Integer> x = new ArrayList<Integer>(); ArrayList<Integer> y = new ArrayList<Integer>(); int a, b, c, d; sum.add((2 * 2 * 2) + (1 * 1 * 1)); x.add(1); y.add(2); int i = 4; while(true) { for(int j = 1; j < i/2 +1; j++) { int k=i-j; int cubeSum = (k * k * k) + (j * j * j); for (int l = 0; l < sum.size(); l++) { a = (int)x.get(l); b = (int)y.get(l); if(cubeSum == sum.get(l)) { if (a != j && a != k && b != j && b != k) { c=j; d=k; System.out.println("The first positive integer " + "expressible as the sum\nof 2 different positive" + " cubes in 2 different ways\nis " + cubeSum + " = " +a+"^3 + "+b+"^3 = " + c+"^3 + "+d+"^3"); return; } } } sum.add(cubeSum); x.add(j); y.add(k); } i++; } } }
I find the rewritten version slightly more readable than the original, though I still can't really understand it.
Now, back to our regularly scheduled programming…
Algorithm
- Magic numbers: You start with
x.add(1), y.add(2), and i = 4. Where did those magic numbers come from? They're not naturally part of the problem, and you didn't explain. x vs. y: What do lists x and y represent? How does a number end up on these lists, why would it appear on x rather than y, or y rather than x?- Commenting: What is the strategy of your code? Please outline it in a comment. Mathematical algorithms in general are complicated, and algorithms, more than anything else, need comments!
- False proof: How do you know that you've found the minimum answer rather than just any answer? I'm not convinced at all. In fact, if you remove the
return after System.out.println() and just let it run, you'll see that it prints 110808 = 6^3 + 48^3 = 27^3 + 45^3before110656 = 4^3 + 48^3 = 36^3 + 40^3. Therefore, the fact that your program prints 1729 is luck, not skill. - Separation of concerns: If you force yourself to separate the code that does input/output from the code that does pure computation, then you will also force yourself to write well organized code.
Proposed Solution
Since your algorithm is bogus, we'll have to start from scratch. I propose an algorithm in which we iterate through n = 1, 2, 3, 4, … until we find one that is the sum of two cubes. Then we test if it is also expressible as a sum of another two cubes. Since we're testing n in increasing sequence, we can be sure that the first result is indeed the minimum number meeting the criteria.
To test whether n is a sum of two cubes, we can successively try subtracting 13, 23, 33, 43, … and test whether the difference is also a perfect cube. To test whether the difference is a perfect cube, we could take its cube root (floating point — nope!), or check it against a list of perfect cubes (better — raising integers to the third power is easy). I've written a class called Cubes to help enumerate all perfect cubes.
There's a lot of verbose supporting code. However, if you look at the heart of the solution, which is hardyRamanujanBreakdown(long n), you'll find it to be very readable.
I've also written it such that you can easily modify the program to find subsequent numbers that are representable as sums of two cubes in two ways. If you let this run infinitely, it's vulnerable to overflow, but you'll have hit CtrlC long before that happens. ☺
It's also slower than your original, but the original strategy is flawed, so it doesn't count.
import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet; ////////////////////////////////////////////////////////////////////// /** * An iterator of positive perfect cubes, starting from 1, and ignoring * overflow. */ class Cubes implements Iterator<Long> { /** * An "infinite" set of all perfect cubes. */ private static SortedSet<Long> allCubes = new TreeSet<Long>(); /** * Helper to generate more members of allCubes as needed. */ private static Cubes allIter = new Cubes(); static { allCubes.add(allIter.next()); } public static boolean isCube(long num) { while (num > allCubes.last()) { allCubes.add(allIter.next()); } return allCubes.contains(num); } public static int cubeRoot(long num) { while (num > allCubes.last()) { allCubes.add(allIter.next()); } return 1 + allCubes.headSet(num).size(); } public static final long cube(int num) { return (long)num * num * num; } private int i = 1; @Override public boolean hasNext() { return true; } @Override public void remove() { throw new UnsupportedOperationException(); } @Override public Long next() { return cube(this.i++); } public Cubes dup() { Cubes moreCubes = new Cubes(); moreCubes.i = this.i; return moreCubes; } } ////////////////////////////////////////////////////////////////////// public class HardyRamanujan implements Iterator<Long> { private long n; private long[] breakdown; public HardyRamanujan() { this.n = 1; } @Override public boolean hasNext() { // Ignores overflow return true; } @Override public void remove() { throw new UnsupportedOperationException(); } @Override public Long next() { while (null == (this.breakdown = hardyRamanujanBreakdown(this.n))) { this.n++; } return this.n++; } /** * Returns the breakdown of the current Hardy-Ramanujan number n as an * array of four perfect cubes [a, b, c, d]. n = a + b = c + d. * a < c <= n/2 <= d < b. Returns null if next() has never been called. */ public long[] breakdown() { return this.breakdown; } private static long[] hardyRamanujanBreakdown(long n) { long a, b, c, d; // Exists n == a + b, where a and b are cubes? Cubes cubes = new Cubes(); while ((a = cubes.next()) < n / 2) { if (!Cubes.isCube(b = n - a)) { continue; } // If so, exists n == c + d, where c and d are cubes, and c > a ? Cubes moreCubes = cubes.dup(); while ((c = moreCubes.next()) <= n / 2) { if (!Cubes.isCube(d = n - c)) { continue; } return new long[] { a, b, c, d }; } } return null; } public static void main(String[] args) { HardyRamanujan hrIter = new HardyRamanujan(); do { long hrNum = hrIter.next(); long[] breakdown = hrIter.breakdown(); System.out.format("%d = %d^3 + %d^3 = %d^3 + %d^3\n", hrNum, Cubes.cubeRoot(breakdown[0]), Cubes.cubeRoot(breakdown[1]), Cubes.cubeRoot(breakdown[2]), Cubes.cubeRoot(breakdown[3])); } while (false); // Change to true to get more! } }
