java - 欧拉项目#14 : Program runs for long time

Question

我正在尝试解决欧拉项目#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  

Which starting number, under one million, produces the longest chain?

这是我尝试过的:

public class Problem14 {
    public static void main(String[] args) {
        int longestLength = 1;
        int longestStart = 1;
        for (int i = 1; i < 1000000; i++) {
            int candidate = getCollatzLength(i);
            if (candidate > longestLength) {
                longestLength = candidate;
                longestStart = i;
            }
        }
        System.out.println("starting point = " + longestStart);
    }

    public static int getCollatzLength(int startingNumber) {
        int length = 1;
        while (startingNumber != 1) {
            startingNumber = getNextCollatz(startingNumber);
            length++;
        }
        return length;
    }

    public static int getNextCollatz(int current) {
        if (current % 2 == 0) {
            return current / 2;
        } else {
            return 3 * current + 1;
        }
    }
}

不幸的是，这个运行时间很长(超过 5 分钟)。知道这里出了什么问题吗？

当我打印产生当前最长链的起始数字时，我得到的最后一个是:

new longest start is 106239

Answer 1

当它达到 113,383 时，链中的某些元素超出了 2^31-1，因此超出了 int 的范围，并且在达到 113,383 之前还会发生许多其他情况一百万。它在链中达到的最大值是 56,991,483,520。如果您从 int 更改为 long 应该没问题。