Project Euler 025

025

フィボナッチ数列は以下の漸化式で定義される:
F_n = F_n-1 + F_n-2, ただし F₁ = 1, F₂ = 1.
最初の12項は以下である.
F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144
12番目の項, F₁₂が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

->次の問題

考え方

シンプルにフィボナッチ数列を順番に出力し、1000桁(10⁹⁹⁹)より大きくなるポイントまでループさせました。
フィボナッチ数列を生成するgeneratorは002で作っていましたが、このときは有限なループとしていたものを無限ループするように変更しました。
フィボナッチ数列の一般項にlog10なんかして計算したらもっと簡単にできるんでしょうか…

math_functions.py

def fibonacci_generator() -> int:
    """fibonacci数列を返すgenerator
    Returns:
        int: fibonacci数列を順に返す
    """
    last_result = 0
    result = 1
    while True:
        yield result
        result, last_result = result + last_result, result

コード

for文とfibonacci_generatorで無限ループを行い、1000桁を超えたところでループを抜けるようにしました。
Javaではループ内で宣言した変数(iやfibonacci_num)はループ外から参照できなかったですが、Pythonは関係なく参照できるんですね。

euler025.py

def main():
    n = 1000  # 1000桁になるのは
    end_point = 10 ** (n - 1)  # 1000桁以上になったら終了
    # enumurateを使いループの何番目かを取得
    for i, fibonacci_num in enumerate(fibonacci_generator()):
        if fibonacci_num > end_point:
            break
    print(f'{n}桁となるのは第{i+1}項')  # iは0から始まるので+1


def fibonacci_generator() -> int:
    """fibonacci数列を返すgenerator
    Returns:
        int: fibonacci数列を順に返す
    """
    last_result = 0
    result = 1
    while True:
        yield result
        result, last_result = result + last_result, result
        

if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaで実行できるようにmath_funcitonsの関数部分も1つのコードに入れました(paizaで自作の関数をimportする方法よくわからない)

paizaにて実行
結果 1000桁となるのは第4782項 0.0007300376892089844 sec