Project Euler 014
正の整数に以下の式で繰り返し生成する数列を定義する.
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万以上になってもよい
->次の問題
考え方
だれでも理解できるシンプルなルールにも関わらず、未解決問題というのはおもしろいですね。
まずはCollatz数列を作るgeneratorを作りました。
def collatz_generator(n: int) -> int:
"""Collatz数列を返すgenerator
Args:
n: Collatz数列の開始点となる自然数
Returns:
int: Collatz数列を順に返す
"""
yield n
while n != 1:
if n % 2 == 0:
n //= 2
yield n
else:
n = n * 3 + 1
yield n
①単純にループで回す。
まず真っ先に思い浮かぶものとして、100万以下の数から始まるCollatz数列を生成→最も長くなるものを選ぶという方法があります。
探索範囲は、
- 50万以上…50万以下の場合は2倍すれば必ず1つ長い数列を作り出せる
- 奇数…感覚的に始めに1/2される偶数より3倍される奇数のほうが長くなりそう
としました。奇数については本当に正しいのかわからないので良くないかもしれません。75より74のほうが長くなったりもするので
[74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[75, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1]
def main():
n = 10 ** 6
max_size = 0
answer = None
for i in range(n // 2 + 1, n, 2): # 範囲は50万以上の奇数
list_size = len(list(collatz_generator(i))) # 数列の長さ
if list_size > max_size:
max_size = list_size
answer = i
print(answer, max_size)
if __name__ == '__main__':
main()
このコードはシンプルですが、時間がかかります(paizaではtimeout、MacBookProで6秒程度)。
②辿った経路を記録しておく
例えば、先に検証した9から始まるCollatz数列の長さ[Collatz(9)]=20を記録しておけば、
18を検証する際に18→9となった時点で後の配列の長さが20であることがわかるので、
全ての数列を計算せずとも長さがCollatz(18) = 21とわかります。
数列の起点となる数とそこからの数列の長さをセットで記録するので辞書型dictを使用します。
既知の数列が出現するまでの数列をストックしていき、既知の数列が出現したらそこから逆順に処理します。
例:
Collatz(7) → [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
→ 17
Collatz(9) → [9, 28, 14,]→次に7が出現
14から逆順に
Collatz(14) = 17 + 1 = 18
Collatz(28) = 17 + 2 = 19
Collatz(9) = 17 + 3 = 20
と計算、計算結果をdictに追加していきます。
コード
import time
def main():
n = 10 ** 6
collatz_dict = {1: 1} # これまで出てきた数列をkey、そのkeyから生成したcollatz数列の長さをvalueとする辞書
number_list = [] # 新しく出現した数列を入れるリスト
for i in range(n // 2 + 1, n, 2): # 探索範囲は50万より上の奇数
number_list.clear()
for collatz in collatz_generator(i):
if collatz in collatz_dict.keys(): # すでに出てきている数字だった場合
# 新しく出現した数列を逆順処理、indexは1から始める
for i, new_collatz in enumerate(reversed(number_list), start=1):
# 新しく辞書に追加
collatz_dict[new_collatz] = collatz_dict[collatz] + i
break
else:
number_list.append(collatz) # これまでになかった数字の場合、リストに加える
max_key = max(collatz_dict, key=collatz_dict.get) # valueが最大となるkeyを取得
print(f'{max_key}のとき最長で{collatz_dict[max_key]}')
def collatz_generator(n: int) -> int:
"""Collatz数列を返すgenerator
Args:
n: Collatz数列の開始点となる自然数
Returns:
int: Collatz数列を順に返す
"""
yield n
while n != 1:
if n % 2 == 0:
n //= 2
yield n
else:
n = n * 3 + 1
yield n
if __name__ == '__main__':
st = time.time()
main()
print(time.time() - st, 'sec')
forが3重、ifもあり、かなり読みづらくなってしまいました。
paizaにて実行
結果
837799のとき最長で525
1.5854110717773438 sec
まだ時間がかかっていますが、総当たりよりは早くなりました。
今回のコードでは全ての数を辞書に保管していましたが、再利用されづらい大きな数字(>100万)を省くことで高速化できるようです。
for i, new_collatz in enumerate(reversed(number_list), start=1):
# 新しく辞書に追加
collatz_dict[new_collatz] = collatz_dict[collatz] + i
ここを以下に変更
for i, new_collatz in enumerate(reversed(number_list), start=1):
if new_collatz < n:
# 新しく辞書に追加
collatz_dict[new_collatz] = collatz_dict[collatz] + i
これで1.1~1.2秒程度に短縮できました。