014. 最长的考拉兹序列(longest Collatz sequence)

对于所有正整数，考虑如下迭代序列：

$$ n\rightarrow \frac{n}{2}\ if\ n\ is\ even,n\rightarrow3n+1\ if\ n\ is\ odd $$

从13开始并使用以上迭代规则，我们可以得到以下序列：

$$ 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1 $$

可以看出这个序列从13开始并到1结束总共包含10个数。考拉兹猜想指出使用以上迭代规则，所有正整数都会最终回到一，虽然这个猜想仍未得到证明。求在一百万以下，那个起始数可以产生最长的考拉兹序列？(注意：序列中包含的数的个数可以超过一百万。)

分析：此题的思路相对直接，只需要把一至一百万之间所有数的考拉兹序列的长度都算出来再求最大值对应的数字即可。可以优化的地方有两点：一是当\(n\)是奇数时，\(3n+1\)必然是偶数，则接下来必定需要除以二，则可以一步走完，也就是说当\(n\)是奇数时可以多算一步，直接计算\((3n+1)/2\)，这样可以更快的到达序列的终点，但注意在计算累计步数时，应该加二而不是加一。另一个可以优化的点是在计算各个数考拉兹序列时，中间过程可能出现之前已经计算过的数字，为了避免重复计算，可以把之前数字对应的序列长度都缓存下来，之后碰到同样的数字，直接引用其值并加上之前已经走过的步数即可。代码如下：

# time cost = 1.26 s ± 105 ms

def main(N=10**6):
    d = {}
    for x in range(2,N):
        i,n = x,0
        while x != 1:
            if x < i:
                n = n + d[x]
                break
            elif x % 2 == 0:
                x = x // 2
                n += 1
            else:
                x = (3*x+1) // 2
                n += 2
        d[i] = n
    return max(d,key=d.get)