読者です 読者をやめる 読者になる 読者になる

Kashiyuki Blog

公務員試験・院試などの情報や物理・天文、たまにプログラミング系

Project Euler 14「最長のコラッツ数列」をPython3で書いてみた[解答]

SPONSORED LINK

コラッツ数列って初めて聞きました。そして特に調べていないので解説もしないです。すみません。

問題文

正の整数に以下の式で繰り返し生成する数列を定義する.

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万以上になってもよい

そして、コード。
今回はあまりに処理に時間がかかったので、時間も計測しました。

import time
start = time.time()
# ここから時間計測開始

countlist = []
n = 1000000

for i in range(2, n):
    while i> 1:
        if i % 2 == 0:
            i = i / 2
            count += 1
        else:
            i = 3*i + 1
            count += 1
    else:
        countlist.append(count)
        count = 0

print(countlist.index(max(countlist)))

elapsed_time = time.time() - start     # 時間計測終了
print("elapsed_time:{0}".format(elapsed_time))    # かかった時間を表示

結果

837797
elapsed_time:59.763405084609985

時間かかりすぎ…(単位は秒)
これはク◯コードですね。
でも10分くらいでパッと組んだコードだし、これから速度上がるコードに改良すればよし!(謎のポジティブ)

このサイトのコードだと9秒くらいでいけるらしいんですけど、このサイトのコードってだいたい難しいんですよね。。

Project Euler: Python solutions