# Generate all possible numbers which can be representated as the sum of 2 cubes below N

I have written a program that generates all possible numbers which can be represented by adding 2 cubes which have value less than N

For example: when $N = 10, 1^3 + 2^3 = 9$

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AllNumberLessThanNasCubes {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("enter an integer n");
int n = new Scanner(System.in).nextInt();

System.out.println("all possible numbers are as follows ");
generateAllPossibleNumbers(n);

}

/**
* This function will generate all possible numbers less the {@link n} which can
* be represented as the sum of 2 cubes
* For eg.when N=10 ,  1^3 + 2^3 = 9
* @param n
*/
public static  void generateAllPossibleNumbers(int n) {
// TODO Auto-generated method stub

List<Long> cubes = new ArrayList<>((int) Math.cbrt(n));
List<Long> allSum = new ArrayList<>();
for (int i=1; Math.pow(i, 3)< n ;++i){
}
long sum=0 , tempSum=0;
int cubesSize= cubes.size();
System.out.println(cubes);
for (int i=0; i < cubesSize ;++i){
sum = cubes.get(i);

for (int j=i+1; j< cubesSize ; ++j){
tempSum = sum + cubes.get(j) ;
//System.out.println(tempSum);
if (tempSum >= n){
break;
}else{
}
}
}
System.out.println(allSum);
}
}


Is this the correct way to solve the problem? Is there an efficient way to solve it?

Except for error checking while taking input, what else can be improved?

• Your question says "by adding 2 cubes". Do you mean "by adding two or more cubes"? – 200_success Feb 23 '15 at 11:55
• I mean by "adding 2 cubes" only. Any 2 cubes will do. Will also write a program for the latter – Aneesh K Feb 23 '15 at 12:00
• Results are obviously incorrect. – 200_success Feb 23 '15 at 12:05
• @200_success : I have given the title correctly. That is a program to generate numbers which can be represented as a sum of 2 cubes. I just added that I will post the program for "2 or more" later since I am still coding it. – Aneesh K Feb 23 '15 at 12:09
• The first few lines of output are 9, 36, 100, …. How are 36 and 100 decomposable as sums of two cubes? – 200_success Feb 23 '15 at 12:11

Except for error checking

Error checking would be nice, and can easily be done, so why not add it to the top of your method:

    if (n < 0) {
throw new IllegalArgumentException("number must not be negative");
}


what else can be improved?

• your formatting, especially your spacing, which seems very random, and thus makes the code hard to read. Just use an IDE to fix this for you.
• define variables in as small a scope as possible. For example, sum can be declared inside the loop as long sum = cubes.get(i);.
• don't print in your method, but return the values instead. This makes the next point a lot easier, and makes your method reusable in general.
• write unit tests to verify the functionality of your code, and to make it a lot easier to make changes without being afraid of breaking the code.
• If I declare long sum inside the loop, java will have to re-declare it every time the loop iterates. Won't it make the execution slower? – Aneesh K Feb 23 '15 at 11:57
• @AneeshK I would assume that the compiler could optimize it. But even if not, such micro-improvements are generally not worth the loss in readability. – tim Feb 23 '15 at 12:05
• @AneeshK You're way too far from how a compiler works. A declaration is gone already when generating the bytecode (i.e. before any optimizations). Forget the microoptimizations, the compiler is damn smart and loves clean code (seriously!). – maaartinus Apr 7 '15 at 20:56

Your code is attempting to print a list of two distinct cubes which you never mentioned in your question. Is there any reason that $1^3 + 1^3$ should not be in the list?

If you want to know all the numbers less than the cube root of n, would you cube each number until one is greater than n or is there a faster way?

for (int i=1; Math.pow(i, 3)< n ;++i)


Since order matters in your list (i < j), can you think of a tighter upper bound for i in the doubly nested for loop?

for (int i=0; i < cubesSize ;++i)


Some of your variable names don't fit their purpose.

sum = cubes.get(i);
tempSum = sum + cubes.get(j);


So sum was never really the sum. Maybe use

a = cubes.get(i);
b = cubes.get(j);
sum = a + b;


As an alternative design approach, in the doubly nested for loop you could calculate the maximum j for each i to eliminate the check (if(tempSum >= n) performed in your program. However with compiler branch prediction I would probably just leave it as is. You could always compare the two approaches.

Kudos for building a list of cubes though. That would not have been part of my initial design but for large N it saves a lot of redundant calculations (at the expense of memory of course).

Code organisation

It would probably make sense to return a list of sums instead of printing it. Also, it you do so, a set seems to be an even better idea as you wouldn't have duplicates.

It's more than overcomplicated. You're supposing that cubes.get(i) is faster than computing the third power. I doubt it. Moreover,

for (int i=1; i<...; ++i) {
int square = i*i;
...
}


can be optimized to

for (int i=1, square=1; i<...; ++i, square+=i+i-1) {
int square = i*i;
}


and similarly for cube. But forget, the compiler knows it well and even if not, multiplication is pretty fast on modern hardware.

So I'd bet that this straightforward method is faster:

public static void printAllCubeSumsBelow(int limit) {
List<Long> result = new ArrayList<>();
for (int i = 0; ; ++i) {
long a = (long) i * i * i; // NOTE 1
if (a >= limit) break;
for (int j = i + 1; ; ++j) {
long b = (long) j * j * j;
long sum = a + b;
if (sum >= limit) break;

NOTE 1: Note that for really big n (close to Integer.MAX_VALUE) i * i * i could overflow, that's why (long ) i * i * i is needed.