Collatz Conjecture

The Collatz conjecture – also known as the 3n+1 problem – provides an interesting programming exercise. The first time I saw it was in the book Programming Challenges and you can also try to submit your solution to the UVa online judge.

The fastest solution I could come up with uses recursion and caching to store previously calculated cycles. The idea is simple: calculate the number of cycles just once for any given number.

The implementation looks a little bit weird because you cannot use long variables to index arrays in Java, as opposed to C and C++. For this reason, my solution only caches values that are sufficiently small.

In any case, here is my solution. Please let me know if you see any possible improvements.

/**
 * Implements a simple cycle calculator for the Collatz conjecture. It uses
 * recursion and array based caching.
 */
public final class Collatz {
    private static final int MAX_SIZE = 1000000;
    private static int[] cache = new int[MAX_SIZE];

    /**
     * Prevents instantiation.
     */
    private Collatz() {}

    /**
     * Calculates the number of cycles for a given number.
     */
    public final static int cyclesForNumber(long n) {
        // Try to return the number of cycles from cache
        if (n < MAX_SIZE) {
            int cycles = cache[(int) n];
            if (cycles > 0) {
                return cycles;
            }
        }

        // Calculate the number of cycles for n
        int cycles = 0;
        if (n == 1) {
            cycles = 1;
        } else if ((n & 1) == 0) {
            cycles = 1 + cyclesForNumber(n >> 1);
        } else {
            cycles = 1 + cyclesForNumber(3 * n + 1);
        }

        // Store it in the cache and return
        if (n < MAX_SIZE) {
            cache[(int) n] = cycles;
        }
        return cycles;
    }

    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        int num1 = 1;
        int num2 = 999999;
        int max = 0;
        for (int i = num1; i <= num2; ++i) {
            int cycles = Collatz.cyclesForNumber(i);
            if (cycles > max) {
                max = cycles;
            }
        }
        System.out.println("cycles: " + max);
        long dt = System.currentTimeMillis() - t0;
        System.out.println("elapsed time: " + dt);
    }
}

Advertisement