最も長いCollatz列

Project Euler 14

正の整数に対して、以下の繰り返しで生成される数列を定義する。

n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

この規則に従い 13 から始めると、以下の数列が生成される。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

この数列（13 から始まり 1 で終わる）は、10項で構成される。しかし、どのような数から開始しても必ず 1 になるということ（Collatzの問題）は未だ証明されていない。

100万未満の数字のうち、最も長い数列を生成するのはどれか？

Note: 項の途中で100万以上になってもよい。

---

$n\in\mathbb{N}$ に対して collatz($n$) で上記の計算結果が得られるものとする。

def collatz(n):
    if n % 2 == 0:
        return n/2
    return 3*n+1

上の例では、1 = collatz(2) = collatz(collatz(4)) = collatz(collatz(collatz(8))) = ･･･ = collatz(collatz(･･･(collatz(13))･･･)) となる。
このとき、13 から始まる collatz 数列の項数は、collatz(13) = 40 から始まる数列の項数に 1 を加えたものであることは自明であり、また、一般性を失わない。

そこで、$n$ の場合の collatz 数列の項数を length[n] として管理すると、length[n] = length[collatz(n)] + 1 となる。
計算量を低減させるため、一度計算した length[n] をそのまま保持することとする。
なお、計算結果の上限が不明であるため、length はリストではなく辞書形式とする。

def get_length(length, n):
    c = collatz(n)
    if c not in length:
        length = get_length(length, c)
    length[n] = length[c] + 1
    return length

length = {1: 1}
max_key = 0
max_value = 0
for i in range(2, 1000000):
    length = get_length(length, i)
    if max_value < length[i]:
        max_value = length[i]
        max_key = i
print max_key, max_value