Why does the java program freeze on 113882?

Question

I wrote a java program that finds the length of the chain of a number using the collatz sequence. The collatz sequence goes: if the number is even, divide it by two, if odd, multiply by 3 and add one. The sequence ends when the number reaches 1. Additional Info on Collatz Sequence. My program finds the chain length of the numbers from 1 to 1 million, but it stops at 113382. No error message is displayed, the program just stops printing out numbers.

*edit: I have tested it, and it turns out that when the program is on 113383, the chain converges to negative values. Can anyone explain this?

I have included the full code, as it is very short.

public static void main(String[] args) {
    int max =0, maxChain=0;
    for(int i = 2; i <1000000; i++ )
    {
        int c =i;
        int counter = 0;
        while(c != 1)
        {
            if(c%2 ==0) c/=2;
            else c= 3*c+1;
            counter++;
        }
        if(counter > maxChain)
        {
            maxChain =counter;
            max = i;
        }
        System.out.println(i);
    }
    System.out.println(max +" has a chain length of " +maxChain);

}

If you put an output statement in the `while` you'll see it doesn't freeze, it never stops. — ChiefTwoPencils, Jan 27 '14 at 04:25
@BobbyDigital then if that's the case, why does it converge to negative values? — A Parikh, Jan 27 '14 at 04:32
Possible duplicate of [What is a debugger and how can it help me diagnose problems](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Raedwald, Jan 29 '16 at 03:39

Bohemian · Accepted Answer · 2014-01-27T04:42:18.393

For the number 113383, iteration #120 yields 827370449. The next iteration numerically yields 2482111348 which is too large to fit in an int variable, so it causes an arithmetic overflow that wraps around to a negative number.

From there, all iterations result in a negative number, and although the result repeatedy cycles through -1, the loop termination condition of the result being 1 never occurs, so an infinite loop results.

However, if you change the variable type to long, you avoid the overflow (for this starting number anyway), and the sequence finishes after 247 iterations.

Incidentally, I found this out by simply printing each iteration and it became immediately obvious what had happened. You could have done the same thing and solved this yourself. Debugging is as handy a skill as coding, because we all hit coding situations that surprise us and finding the reason yourself is always more satisfying and memorable (so you don't fall for the same trap again).

Thanks Bohemian, I forgot about the max value turning into the min value in Java. That would explain the negative numbers and the infinite loop. I'll use BigInteger because the same problem may occur with long sometime in the future. — A Parikh, Jan 27 '14 at 04:44

Why does the java program freeze on 113882?

1 Answers1