collatz sequence - optimising code

Question

As an additional question to an assignment, we were asked to find the 10 starting numbers (n) that produce the longest collatz sequence. (Where 0 < n < 10,000,000,000) I wrote code that would hopefully accomplish this, but I estimate that it would take a full 11 hours to compute an answer.

I have noticed a couple of small optimisations like starting from biggest to smallest so adding to the array is done less, and only computing between 10,000,000,000/2^10 (=9765625) and 10,000,000,000 because there has to be 10 sequences of longer length, but I can't see anything more I could do. Can anyone help?

Relevant Code The Sequence Searching Alg

long[][] longest = new long[2][10]; //terms/starting number
long max = 10000000000l; //10 billion

for(long i = max; i >= 9765625; i--) {
    long n = i;
    long count = 1; //terms in the sequence

    while(n > 1) {
        if((n & 1) == 0) n /= 2; //checks if the last bit is a 0
        else {
            n = (3*n + 1)/2;
            count++;
        }
        count++;
    }
    if(count > longest[0][9]) {
        longest = addToArray(count, i, longest);
        currentBest(longest); //prints the currently stored top 10
    }
}

The storage alg

public static long[][] addToArray(long count, long i, long[][] longest) {
    int pos = 0;
    while(count < longest[0][pos]) {
        pos++;
    }
    long TEMP = count; //terms
    long TEMPb = i; //starting number
    for(int a = pos; a < longest[0].length; a++) {
        long TEMP2 = longest[0][a];
        longest[0][a] = TEMP;
        TEMP = TEMP2;

        long TEMP2b = longest[1][a];
        longest[1][a] = TEMPb;
        TEMPb = TEMP2b;
    }
    return longest;
}

Answer 1

You can do something like

while (true) {
    int ntz = Long.numberOfTrailingZeros(n);
    count += ntz;
    n >>>= ntz; // Using unsigned shift allows to work with bigger numbers.
    if (n==1) break;
    n = 3*n + 1;
    count++;
}

which should be faster as it does multiple steps at once and avoids unpredictable branches. numberOfTrailingZeros is JVM intrinsic taking just one cycle on modern desktop CPUs. However, it's not very efficient as the average number of zeros is only 2.

The Wikipedia explains how to do multiple steps at once. This is based on the observation that knowing k least significant bits is sufficient to determine the future steps up to the point when the k-th halving happens. My best result based on this (with k=17) and filtering out some non-promising values is 57 seconds for the determination of the maximum in range 1 .. 1e10.