DouKaku?

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Sample120 {
    private final long maxIndex_;
    private final Map<Long, Long> memo = new HashMap<Long, Long>();

    public Sample120(int max) {
        long maxInd = 0;
        long maxLen = 0;
        List<Long> sequence = new ArrayList<Long>();
        for (long index = 1; index <= max; index++) {
            sequence.clear();
            long len = calc3n1(index, 0, sequence);
            createMemo(len, sequence);
            if (maxLen < len) {
                maxLen = len;
                maxInd = index;
            }
        }
        maxIndex_ = maxInd;
    }
    private long calc3n1(long x, long length, List<Long> sequence) {
        sequence.add(x);
        if (x == 1) return length;

        Long longVal = memo.get(x);
        if (longVal != null) return length + longVal.longValue();

        if ((x & 1) == 0) {
            return calc3n1(x / 2, length + 1, sequence);
        } else {
            return calc3n1(3 * x + 1, length + 1, sequence);
        }
    }
    private void createMemo(long length, List<Long> sequence) {
        long len = length;
        for (int index = 0, max = sequence.size(); index < max; index++) {
            Long longVal = sequence.get(index);
            if (memo.get(longVal) == null) {
                memo.put(longVal, len--);
            }
        }
    }

    public long getMaxIndex() {
        return maxIndex_;
    }
    public long getMaxLength() {
        return memo.get(maxIndex_);
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        Sample120 instance = new Sample120((int)Math.pow(2, 20));
        System.out.println(instance.getMaxIndex() + ":" + instance.getMaxLength());

        long end = System.currentTimeMillis();
        System.out.println("elapse: " + (end - start) + "(ms)");
    }
}