Coursera - Computer Science: Programming With A Purpose

Week 7: Performance - Ramanujan Numbers

When the English mathematician G. H. Hardy came to visit the Indian mathematician Srinivasa Ramanujan in the hospital one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, No, Hardy! No, Hardy! It is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.

An integer n is a Ramanujan number if it can be expressed as the sum of two positive cubes in two different ways. That is, there are four distinct positive integers a, b, c, and d such that n = a 3 + b 3 = c 3 + d 3. For example 1729 = 13 + 123 = 93 + 103.

Write a program Ramanujan.java that takes a long integer command-line argument n and prints true if it is a Ramanujan number, and false otherwise. To do so, organize your program according to the following public API:

public class Ramanujan {

    // Is n a Ramanujan number?
    public static boolean isRamanujan(long n)

    // Takes a long integer command-line arguments n and prints true if
    // n is a Ramanujan number, and false otherwise.
    public static void main(String[] args)
}

Here are a few sample executions:

~/Desktop/performance> java Ramanujan 1729
true

~/Desktop/performance> java Ramanujan 3458
false

~/Desktop/performance> java Ramanujan 4104
true

~/Desktop/performance> java Ramanujan 216125
true

~/Desktop/performance> java Ramanujan 9223278330318728221
true

Your program should take time proportional to n1/3 in the worst case. It should be fast enough to process any 64-bit long integer in a fraction of a second.

Note: the above description is copied from Coursera and converted to markdown for convenience

Solution:

public class Ramanujan {

    // Is n a Ramanujan number?
    public static boolean isRamanujan(long n) {
        long firstA = 0;
        long firstB = 0;
        int count = 0;

        // if minA = 1, then maxA cannot be larger than cbrt(n)
        final long minA = 1;
        final long maxA = (long) Math.cbrt(n);
        for (long a = minA; a < maxA; a++) {
            final long curA = a * a * a;
            // if curA, then the only possible value for b is cbrt(n - curA)
            final long b = (long) Math.cbrt(n - curA);
            final long curB = b * b * b;
            final long ab = curA + curB;
            if (ab == n) {
                if (count == 0) {
                    count++;
                    firstA = a;
                    firstB = b;
                } else if ((firstA != b) && (firstB != a)) { // make sure not reversed
                    count++;
                }
                if (count > 1) {
                    return true; // found two positive cubes in two different ways
                }
            }
        }
        return false;
    }

    // Takes a long integer command-line arguments n and prints true if
    // n is a Ramanujan number, and false otherwise.
    public static void main(String[] args) {
        final long n = Long.parseLong(args[0]);
        StdOut.print(isRamanujan(n));
    }
}

Link To: Java Source Code