Help us understand the problem. What is going on with this article?

Project Euler 014を解いてみる。「最長のコラッツ数列」

Project Euler 014

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を作りました。

math_functions.py
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に追加していきます。

コード

euler014.py
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秒程度に短縮できました。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away