Is n a Ramanujan number--why am I getting errors in values near 2^63?

Question

Given a number, test to see if it is a Ramanujan number (defined in our course as the sum of two cubes two different ways). It must run in n^(1/3) time.

My code is working--sometimes. As test values approach 2^63 -1 I am getting some random errors.

Weirdly, I was passing this test for numbers in that range before I changed the starting value of a counter to fix a different bug. Can anyone tell me why this might be?

I set up a for loop to create values for a^3.

Then I set values for b=(n-a^3)^(1/3).

Then I test b to see if it is an integer. If so, break the loop.

Inserted an if test here to get the code to work, though I have NO IDEA WHY THIS IS NEEDED, and that's the gist of this question. This if statement sets up two different for loops for values above and below n=2^63

Second loop for n < 2^63, starts off with c=a+1 so I don't duplicate. It's the same as the first one.

Second loop for n > 2^63 starts off with c=a.

Why would this make a difference? Why isn't the same code working for smaller and larger numbers?

Sorry for the babyish code, I am just starting out, and a lot of functions are off limits in my course. (For example, I couldn't use floor() and was not allowed to write my own function for it, either).

public class Ramanujan {
public static boolean isRamanujan(long n) {
    if (n <= 0) return false;
    long a3 = 0;
    long c3 = 0;
    double b = 0;
    double d = 0;
    for (int a = 1; a < n; a++) {
        a3 = (long) a * a * a;
        if (a3 > n) break;
        b = Math.cbrt(n - a3);
        if (b == (int) b) break;
    }
    if (n > Math.pow(2, 62)) {
        for (int c = (int) Math.cbrt(a3); c < n; c++) {
            c3 = (long) c * c * c;
            if (c3 > n) break;
            d = Math.cbrt(n - c3);
            if (d == (int) d) break;
        }
    }
    else {
        for (int c = (int) Math.cbrt(a3) + 1; c < n; c++) {
            c3 = (long) c * c * c;
            if (c3 > n) break;
            d = Math.cbrt(n - c3);
            if (d == (int) d) break;
        }
    }
    if (a3 + (long) b * b * b == c3 + (long) d * d * d && b * b * b != c3) 
return true;
    return false;
}

public static void main(String[] args) {
    long n = Long.parseLong(args[0]);
    StdOut.println(isRamanujan(n));

}
}

Any insight as to why I needed to differentiate between larger and smaller numbers?

Answer 1

You'll get weird results when n exceeds the value a long can hold, i.e. Math.pow(2, 63) == Long.MAX_VALUE. At that point, n will experience a numerical overflow.

final long l = Long.MAX_VALUE; // == 2^63
System.out.println(l); // 9223372036854775807
System.out.println(l + 1); // -9223372036854775808

Answer 2

You get random errors for large int values because of arithmetic overflow when Math.cbrt(a3) or even Math.cbrt(n - a3) exceeds the range of type int. You should use type long for all integer variables to reduce this possibility and make sure intermediary results do not exceed the range of type long.

Here is a simpler implementation using a single loop, computing the number of ways:

public class Ramanujan {
    public static boolean isRamanujan(long n) {
        if (n <= 0) return false;
        int count = 0;
        for (long a = 1;; a++) {
            long a3 = a * a * a;
            if (a3 > n - a3) break;
            long b = (long)Math.cbrt(n - a3);
            if (a3 + b * b * b == n) count++;
        }
        return count >= 2;
    }
    public static void main(String[] args) {
        if (args.length == 1) {
            long n = Long.parseLong(args[0]);
            StdOut.println(isRamanujan(n));
        } else
        if (args.length == 2) {
            long n1 = Long.parseLong(args[0]);
            long n2 = Long.parseLong(args[1]);
            for (long n = n1; n <= n2; n++) {
                if (isRamanujan(n))
                    StdOut.println(n);
                if (n == Long.MAX_VALUE) // handle n2 == Long.MAX_VALUE
                    break;
            }
        } else {
            StdOut.println("usage: Ramanujan n1 [n2]");
        }
    }
}

Answer 3

The largest number a long can hold (in Java) is (2 ^ 63) - 1 (Long.MAX_VALUE). Why are you calculating Math.cbrt(a3) ? If a3 = a * a * a, then you already know what Math.cbrt(a3) is.

There is a problem in your code if n > 9223372036854774272 Math.cbrt of 9223372036854774273 is 2097152 and if you cube that you get a negative number because of overflow.

Answer 4

The issue is with multiplying variables a and c of type int to calculate the cube. Need to cast each of the variable to long that is being multiplied.

Example, a3 = (long) a * (long) a * (long) a;