为什么循环会死？(Collat​​z猜想)

Question

我正在尝试使用java进行一些数学运算,如果它(un)均匀,它会测试一个数字,只要它变为1就可以改变它.

我尝试运行我的循环999999次,它似乎陷入约120000次.好吧,它不是停留在Exception中,只是觉得编译器卡住了.

我对Java不太好,有人可以解释一下这里发生了什么吗？

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

你有一个溢出因为3 * n + 1变大了Integer.MAX_VALUE.因此n得到否定而while循环永远不会停止.

使用long而不是int为n!

如果你想检查溢出:

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

Java 8的补充

从Java 8开始,Math该类为"精确"算术(加法,减法,乘法,除法)提供了额外的静态方法,以便ArithmeticException在出现溢出时抛出.使用这些方法,代码可以简化:

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