Python で Project Euler #14「最長のコラッツ数列」 #Python

Problem 14 「最長のコラッツ数列」

正の整数に以下の式で繰り返し生成する数列を定義する.
n → n/2 (n が偶数)\\
n → 3n + 1 (n が奇数)
13からはじめるとこの数列は以下のようになる.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

注意: 数列の途中で100万以上になってもよい

Python

n = 1000000
seq = range(1, n)

collatz_dict = {1: [1]}

def compute_collatz(i):
  if(i not in collatz_dict):
    if(i % 2 == 0):
      collatz = [i] + compute_collatz(i / 2)
    else:
      collatz = [i] + compute_collatz(3 * i + 1)
    collatz_dict[i] = collatz
  return collatz_dict[i]

collatz_lenghs = {}

for i in seq:
  collatz = compute_collatz(i)
  collatz_lenghs[i] = len(collatz)

max_length = max(collatz_lenghs.values())

max_index = collatz_lenghs.values().index(max_length)
max_length_collatz_key = collatz_lenghs.keys()[max_index]
max_length_collatz = collatz_dict[max_length_collatz_key]

result = max_length_collatz_key

print result
print result == 837799
print max_length
print max_length_collatz[:6]

結果

837799
True
525
[837799, 2513398, 1256699, 3770098, 1885049, 5655148]

ちょっと遅いんだけど、いい方法が思いつかない。