Too long runtime of euler project #14 in Java

Question

My code of Euler Project 14 is below. I have run this code for more than 3 hours with output result and it seems to be infinite. When I test a single number such as 11, 27, it will output the collatz chain number:14 and 111 quickly. But I don't know why it couldn't output 1000000 number's max chain number.

/*Problem 14
 * The following iterative sequence is defined for the set of positive integers:
 *          n -> n/2 (n is even)
 *          n -> 3n + 1 (n is odd) 
 * Using the rule above and starting with 13, we generate the following sequence:
 *               13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
 * It can be seen that this sequence (starting at 13 and finishing at 1) contains 
 * 10 terms. Although it has not been proved yet (Collatz Problem), it is thought 
 * that all starting numbers finish at 1.
 * 
 * Which starting number, under one million, produces the longest chain?
 * 
 * NOTE: Once the chain starts the terms are allowed to go above one million.
 */
package number;  
public class LongestCollatzSequence {
    public static int collatzNum(int n){
        int count = 0;
        while(n != 1){
            if(n%2 == 0)
                n = n/2;
            else 
                n = 3*n + 1;
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        int max = 0;
        for(int i = 10; i <= 1000000; i++){
            if(collatzNum(i) > collatzNum(max))
                max = i;
        }
        System.out.println(max);
    }
}

Furthermore, I turn for(int i = 10; i <= 1000000; i++) to for(int i = 10; i <= 10; i++), such a short list of numbers, it is still running all the time without output. What's wrong with my code?

Here is another person's resolution, rianjs.net the code is :

public class Problem014
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        LinkedList<Long> list = new LinkedList<Long>();
        long length = 0;
        int res = 0;
        for(int j = 10; j < 1000000; j++){
            long i = j;
            while (i != 1){
                if (i % 2 == 0){
                    i /= 2;
                    list.add(i);
                }
                else{
                    i = (3 * i) + 1;
                    list.add(i);
                }
            }
            if(list.size() > length){
                length = list.size();
                res = j;
            }
            list.clear();
        }
        long end = System.currentTimeMillis();
        System.out.println(res+" with chain size: "+ length);
        System.out.println(end-begin + "ms");
    }
}

His code runs well, I want to know why my code cannot get the output and what makes the difference of the two resolution?

Answer 1

The argument int n of your collatzNum function will overflow for the value 113383. As you can see, the other implementation uses a long variable for the temporary value.

In addition to that, you can optimize your code a lot by not calculation collatzNum(max) for each loop iteration, but only when max actually changes, in which case you already have the new collatzNum(max)as a return value from collatzNum(i).

Answer 2

You are recalculating the length of the longest number found so far, every time. If you just remembered the longest one you have seen so far it would cut it down to seconds.

BTW If you want to go much faster you can use memorization of all previous values.

static final short[] cache = new short[1000000];

public static int collatzNum(long n) {
    if (n == 1) return 1;
    if (n < cache.length) {
        int count = cache[((int) n)];
        if (count > 0)
            return count;
    }
    int next = (n & 1) == 0
            ? 1 + collatzNum(n >> 1)
            : 2 + collatzNum((n * 3 + 1) >> 1);
    if (n < cache.length)
        cache[((int) n)] = (short) next;
    return next;
}

static {
    for (int i = 10; i < cache.length; i *= 2)
        collatzNum(i - 1);
}

public static void main(String... ignored) {
    long start = System.nanoTime();
    int maxCount = 0, max = 0;
    for (int i = 1; i < 1000000; i++) {
        int count = collatzNum(i);
        if (count > maxCount) {
            maxCount = count;
            max = i;
        }
    }
    long time = System.nanoTime() - start;
    System.out.println("count=" + maxCount + ", value=" + max + ", took=" + time / 1000 / 1000.0 + " ms.");
}

takes about 19 milli-seconds on my laptop.

Note: the result of odd * 3 + 1 is always even so you know you can divide it by 2.

Answer 3

Here is another solution. It is not as efficient as Peter's answer, but it is easier to understand:

public class P14 {

    public static void main(String[] args) {
        getMaxLength(1000000);
    }

    private static void getMaxLength(int threshold) {
        long maxLength = 1;
        int nr = -1;
        for (int i = 3; i < threshold; i++) {
            long sequenceSize = getSequenceSize(i);
            if (sequenceSize > maxLength) {
                maxLength = sequenceSize;
                nr = i;
            }
        }
        System.out.println(nr);
    }

    private static long getSequenceSize(int n) {
        long x = n;
        long count = 1;
        while (x > 1) {
            if ((x & 1) == 0) {        // x%2==0
                x = x >> 1;            // x=x/2
                count++;               // count=count+1
            } else {
                x = x + x + x + 1;     // x=3*x+1
                x = x >> 1;            // x=x/2
                count+=2;               
            }
        }
        return count;
    }

}

Time: 1.5 seconds (Peter's solution takes 0.142 seconds on my machine)

It can be considerably improved using the following observation: if we have x, 2*x will have one more step in the sequence (because 2*x is even). This is why we can ignore numbers that are less than one half. So, using the following getMaxLength method:

    private static void getMaxLength(int threshold) {
        long maxLength = 1;
        int nr = -1;
        int start = (threshold>>1) - 1;      // start = threshold/2 - 1
        for (int i = start ; i < threshold; i++) {
            long sequenceSize = getSequenceSize(i);
            if (sequenceSize > maxLength) {
                maxLength = sequenceSize;
                nr = i;
            }
        }
        System.out.println(nr);
    }

the computation will take about 0.8 seconds.

Answer 4

Here is another solution to the problem using a mixture of iteration & recursion. I hope it helps, I have also provided some comments within the code to help understand it better.

private static int currentLongestChain = 1;

private static long number = 0;

public static void main(String[] args) {
    //TimeTable();
    PE_Problem_14();
}

private static void PE_Problem_14(){
    int longestChain = 1; // store longest chain
    for(long currentNumber = 1; currentNumber < 1000000; currentNumber++){
         if(currentNumber % 2 == 0){
            PE_Problem_14_even(currentNumber); // if currentNumber is even then invoke even helper method
         }else{
            PE_Problem_14_odd(currentNumber); // if currentNumber is odd then invoke odd helper method
         }

         if(currentLongestChain > longestChain){
            longestChain = currentLongestChain;  // update longestChain
            number = currentNumber;
            currentLongestChain = 0;
         }else{
            currentLongestChain = 0;
        }
    }
    System.out.println("longest chain: " + longestChain + " number: " + number); // print the result to the console screen
}

private static void PE_Problem_14_even(long evenNumber) {  // recursive method
    if(evenNumber <= 1) return;
    long localResult = (evenNumber/2);
    if(localResult % 2 != 0){
        ++currentLongestChain;
        PE_Problem_14_odd(localResult);
    }else {
        ++currentLongestChain;
        PE_Problem_14_even(localResult);
    }
}

private static void PE_Problem_14_odd(long oddNumber){  // recursive method
    if(oddNumber <= 1) return;
    long localResult = (3*oddNumber)+1;
    if(localResult % 2 == 0){
        ++currentLongestChain;
        PE_Problem_14_even(localResult);
    }else{
        ++currentLongestChain;
        PE_Problem_14_odd(localResult);
    }
}