考虑如下定义在正整数集上的迭代规则: \begin{align*} &n\mapsto n/2 \text{ ($n$是偶数)}, \\ &n\mapsto 3n+1 \text{ ($n$是奇数)}. \end{align*} 从$13$开始，可以迭代生成如下的序列：: $$13\mapsto40\mapsto20\mapsto10\mapsto5\mapsto16\mapsto8\mapsto4\mapsto2\mapsto1.$$ 可以看出这个序列（从$13$开始到$1$结束）共有$10$项。“冰雹猜想”提出，从任何数开始的上述迭代最终总能得到$1$。在小于一百万的数中，从哪个数开始迭代生成的序列最长？

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

本题难度:

解答

直接搜索，为避免重复计算，我们用一个字典来存放已计算过的数字及其序列长度。结果是 $837799$ (长度为$525$)。

collatzDict={1:1, 2:2, 4:3, 8:4, 16:5, 32:6, 64:7, 128:8, 256:9, 512:10, 1024:11, 2048:12, 4096:13, 8192:14, 16384:15, 32768:16, 65536:17, 131072:18, 262144:19, 524288:20}
maxSeq=0
maxN=0

for i in range(1000000):
    m=i+1
    iSeq=[m]
    step=0
    while m not in collatzDict:
        if m%2==0:
            m=m/2
        else:
            m=3*m+1
        iSeq.append(m)
        step=step+1
    for j in iSeq:
        collatzDict[j]=collatzDict[m]+step
        step=step-1
    if collatzDict[i+1]>maxSeq:
        maxSeq=collatzDict[i+1]
        maxN=i+1

print maxSeq, maxN