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