問題
正の整数に以下の式で繰り返し生成する数列を定義する.
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万以上になってもよい
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014
回答方針
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
の数列で言うと、13で生成される数列の長さは、40で生成される数列の長さに1を足したものである。
つまり、13で生成される数列の長さは、再帰的に求められる。また、途中の結果を記憶しておくことで、計算量を削減することができる。
コード
def next(n):
if n % 2:
return n*3 + 1
else:
return n / 2
def add(dict,n1):
n2 = next(n1)
if not n2 in dict:
dict = add(dict,n2)
dict[n1] = dict[n2]+1
return dict
def main():
dict = {1:1}
(max_i,max) = (1,1)
for i in range(2,10**6):
if not i in dict:
dict = add(dict,i)
if dict[i] > max:
(max_i,max) = (i,dict[i])
print (max_i,max)
結果
2.87secと鬼のように遅い結果となった。ネットを検索してみたところ、ある一定数より大きい数字(100万)については記憶しないようにすることにより、速度を向上させているコードがあった。