Speeding up 3n+1 challenge I have been trying to make this code go faster by trying to write it more efficiently and I don't know what else to do. I got it to 30 seconds but I have seen 23 and 24 and I have no idea on how to do it.    

public class Main {

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

        for(long n = 1; n &lt;= 100000000; n+=2){
            long value = cycleLength(n);
            if(value &gt; (n*n)){
                System.out.println(n + " " + value);
            }
        }

        long endTime = System.currentTimeMillis();

        System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");

    }//main

    public static long cycleLength(long n) {
        long hi = n;

        while (n &gt; 1) {
            if((n&amp;1)==0)  // bitwise AND
                n = n &gt;&gt; 1;  // n even
            else {
                n = 3*n+1; // n odd

                if(hi &lt; n)
                    hi = n;
                n = n &gt;&gt; 1;
            }
        }

        return hi;
    }

}
This code runs in 2 secs vs the original 24 secs in my box, with no additional memory needed, or 0.5 secs if you don't mind using more than 1 CPU.

Going to explain how it works with an example:

Let say that "n" is 97. 
At this point maxSoFar is 9232 (which is the value of cycleLength for 27, 31, 41, ...), which is the maximun value of cycleLength found for all "n" &lt; 97.
97 * 97 is 9409 which is bigger than 9232, which means that if inside the loop of the cycleLength, "j" becomes smaller than 97, then cycleLength will be at most 9232, which is smaller than 9409 so it is not necessary to continue doing any calculations as cycleLenght will be never bigger than n * n.

So with "n" 97, n_square is 9409. We do the first loop, which means that "j" is 292. As "j" > "n", we still have hope that it can become bigger than 9409. Two cycles latter, "j" becomes 73 (292 / 2 / 2). Now we know that 73 is never going to be bigger than 9232, which means that there is no point of searching anymore and we can exit cycleLength.

Note that with this implementation cycleLength for 97 actually return 73 (instead of 9232 of your implementation) but the results are still correct.

The code is basically the same as yours but adding a condition in the cycleLength loop.

public class Main {

private static long maxSoFar = -1;

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

for (long n = 1; n &lt;= 100000000; n += 2) {
  long value = cycleLength(n);
  if (value &gt; (n * n)) {
    System.out.println(n + " " + value);
    maxSoFar = Math.max(value, maxSoFar);
  }
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");
}//main

public static long cycleLength(long j) {
long hi = j;
long original = j;
long n_square = j * j;
while (j &gt; 1) {
  if (j &lt; original &amp;&amp; maxSoFar &lt; n_square) {
    return hi;
  }
  if ((j &amp; 1) == 0)  // bitwise AND
  {
    j = j &gt;&gt; 1;  // n even
  } else {
    j = 3 * j + 1; // n odd
    if (hi &lt; j) {
      hi = j;
    }
    j = j &gt;&gt; 1;
  }
}

return hi;
}

}


The multithreaded version creates a bunch of threads each one calculating a different serie of n. So for 2 threads:
Thread 1 will do 1, 5, 9, 13 ...
Thread 2 will do 3, 7, 11, 15 ...

In my box (4 cores) the optimal value for n = 10^8 is 32 threads.

import java.util.concurrent.ConcurrentHashMap;

public class Main implements Runnable {

private long maxSoFar = -1;
private int start;
private int step;
static ConcurrentHashMap results = new ConcurrentHashMap();

public Main(final int start, final int step) {
  this.start = start;
  this.step = step;
}

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

Thread[] threads = new Thread[32];

for (int i = 0; i &lt; threads.length; i++) {
  threads[i] = new Thread(new Main((i * 2) + 1, threads.length * 2));
}

for (Thread thread : threads) {
  thread.start();
}

for (Thread thread : threads) {
  thread.join();
}

System.out.println("results = " + results);

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");

}

public void run() {
long startTime = System.currentTimeMillis();

for (long n = start; n &lt;= 100000000; n += step) {
  long value = cycleLength(n);
  if (value &gt; (n * n)) {
    System.out.println(Thread.currentThread().getName() + " " + n + " " + value);
    results.put(n, value);
    maxSoFar = Math.max(value, maxSoFar);
  }
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + Thread.currentThread().getName() + " " + (endTime - startTime) + " milliseconds");
}//main

public long cycleLength(long j) {
long hi = j;
long original = j;
long n_square = j * j;
while (j &gt; 1) {
  if (j &lt; original &amp;&amp; maxSoFar &lt; n_square) {
    return hi;
  }
  if ((j &amp; 1) == 0)  // bitwise AND
  {
    j = j &gt;&gt; 1;  // n even
  } else {
    j = 3 * j + 1; // n odd
    if (hi &lt; j) {
      hi = j;
    }
    j = j &gt;&gt; 1;
  }
}

return hi;
}

}