Collatz sequence - optimizing code

Question

As an additional question to the task, we were asked to find 10 starting numbers (n) that form the longest sequence of collatz. (Where 0 <n <10,000,000,000) I wrote a code that we hope will accomplish this, but I believe that it only takes 11 hours to calculate the answer.

I noticed a couple of small optimizations, such as starting from the largest to the smallest, so adding to the array is less and only calculating between 10,000,000,000/2 ^ 10 (= 9765625) and 10,000,000,000, because there should be 10 sequences longer but I see nothing more that I could do. Can anyone help?

Matching Code Alg Sequence Search

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 } } 

Storage vault

 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 since it takes several steps at the same time and avoids unpredictable branches. numberOfTrailingZeros is a built-in JVM that takes only one cycle on modern desktop processors. However, it is not very effective, as the average number of zeros is only 2.

Wikipedia explains how to complete several steps at once. This is based on the observation that knowing the k least significant bits is enough to determine future steps to the point where k -th halfving occurs. My best result based on this (with k=17 ) and filtering out some intangible values is 57 seconds to determine the maximum value in the range 1 .. 1e10 .