why does the loop die? ( Collatz conjecture )

Question

i am trying some math-operations with java, that does test a number if its (un)even and alter it as long as it gets to 1.

I try to run my loop for 999999times, it seems to get stuck at around ~120000times. Well, it is not stopping with an Exception, it just feels like the compiler got stuck.

I'm not that good with Java, can someone explain me what is happening here?

public static void main(String[] args) {

    int n = 0;
    int highestNumber = 0;
    int highestCounter = 0;
    int counter = 0;
    for (int i = 2;i<1000000;i++) {

        if (i%10000==0) {
            System.out.println(i);
        }
        n = i;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber);  
}

Answer 1

You've got an overflow because 3 * n + 1 became larger than Integer.MAX_VALUE. So n gets negative and the while loop will never halt.

Use long instead of int for n!

If you want to check for the overflow instead:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        if (n > (Integer.MAX_VALUE - 1) / 3) {
            throw new RuntimeException("overflow!");
        }
        n = 3 * n + 1;
    }
    counter++;
}

Addition for Java 8

Since Java 8, the Math class provides additional static methods for 'exact' arithmetics (addition, subtraction, multiplication, division) that throw an ArithmeticException in case of an overflow. Using these methods, the code can be simplified:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        n = Math.addExact(Math.multiplyExact(3, n), 1);
    }
    counter++;
}

Answer 2

You have an overflow problem. Change the code like this and you see it:

    while (n!=1) {
        if(n < 0) throw new IllegalStateException("n should not become < 0" + n + "-" + counter);
        if(n > ((Integer.MAX_VALUE -1) / 3)) System.out.println("n too large. " + n);
        if (n%2==0) {   
            n = n/2;
        } else {    
            n=3*n+1;
        }
        counter++;
    }

if you make n to a long it works fine.

Answer 3

This correction works:

public static void main(String []args){
    long highestCounter = -1;
    long highestNumber = -1;
    for (long i = 2;i<1000000;i++) {

        if (i%1000==0) {
            System.out.println(i);
        }
        long n = i;
        long counter = 0;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber); 
}

Answer 4

Hmm, your code looks fine to me. You're solving a pretty typical problem

Is n an integer? If it's a short you might be overflowing it.

Other than that, an integer's max value is over 2 billion, so you shouldn't be hitting it. Just in case, try setting n to a long to see if that helps

Edit: Take for example, the number 77671 According to a blog I read (read: untested) the highest n for i = 77671 is 1,047,216,490

So I think n should be a long, now that I think more about it

Answer 5

You simply running an infinite loop inside while block, add System.out.println(counter); after counter++ to see what's going on..