Problem 14

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

$n \rightarrow n/2$ ($n$ is even)

$n \rightarrow 3n + 1$ ($n$ is odd)

Using the rule above and starting with $13$, we generate the following sequence:

$$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

It can be seen that this sequence (starting at $13$ and finishing at $1$) contains $10$ terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at $1$.

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

NOTE: Once the chain starts the terms are allowed to go above one million.

最长考拉兹序列

考虑如下定义在正整数集上的迭代规则：

$n \rightarrow n/2$ （若$n$为偶数）

$n \rightarrow 3n + 1$ （若$n$为奇数）

从$13$开始，可以迭代生成如下的序列：

$$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

可以看出这个序列（从$13$开始到$1$结束）共有$10$项。尽管还未被证明，但普遍认为，从任何数开始最终都能抵达$1$并结束（这被称为“考拉兹猜想”）。

在小于一百万的数中，从哪个数开始迭代生成的序列最长？

注：在迭代过程中允许出现超过一百万的项。