砂場で遊ぼう

c++/python/mathematica などの練習帳

トップ > project euler > Project Euler 002 / 偶数のフィボナッチ数（Even Fibonacci numbers）

Project Euler 002 / 偶数のフィボナッチ数（Even Fibonacci numbers）

project euler python

問題概略

400 万以下で偶数値のフィボナッチ数の総和を求めよ。
https://projecteuler.net/problem=2

2 で割った余りの周期性を利用

n 番目のフィボナッチ数を f(n) であらわして，これを 2 で割った余りを考えます。

f(n+2)=f(n+1)+f(n),\, f(1)=f(2)=1

\therefore f(n+2)\equiv f(n+1)+f(n),\, f(1)\equiv f(2)\equiv 1\pmod{2}

この漸化式を繰り返し使うと 2 で割った余りは「1, 1, 0」を繰り返すことがわかります。
400 万以下の f(3n) の和を求めればいいわけです。

フィボナッチ数を求めるのに sympy を使いました。
f(3n) が 400 万以下になる最大の n\ (=n_0) を求めて， f(3) から f(3n_0) までの和を求めます。

    import sympy

    nmx = 1
    while sympy.fibonacci(nmx) < 4 * 10 ** 6:
        nmx += 1
    
    print(sum([sympy.fibonacci(n) for n in range(3, nmx, 3)]))

漸化式を使う

g(n)=f(3n) とおいて， g(n) の漸化式を使って計算します。

f(n+2)=f(n+1)+f(n) の特性方程式は x^{2}-x-1=0 です。
これの解を \alpha, \beta とおくと解と係数の関係から

\alpha+\beta=1,\, \alpha\beta=-1

f(n) は A\alpha^n+B \beta^n の形に書けます。

g(n)=f(3n)=A\alpha^{3n}+B \beta^{3n}=A(\alpha^{3})^n+B (\beta^{3})^n

g(n) の特性方程式の解は \alpha^3, \beta^3 です。
簡単な計算で \alpha^{3}+\beta^{3}=4, \alpha^{3}\beta^{3}=-1 がわかるので g(n) の特性方程式は x^{2}-4x-1=0 で，漸化式は

g(n+2)=4g(n+1)+g(n)\mbox{　……(1)}

実は条件をみたす項は 11 個しかなく，この漸化式で g(1)～ g(11) を求めて足せばいいのですが，後学のためもう少し変形します。

S(n)=\sum_{k=1}^n g(k) とおきます。 S(1)=g(1)=f(3)=2 で

g(n)=S(n)-S(n-1)\mbox{　……(2)}\quad (n\geqq 2)

(2)を(1)に代入して整理します。

S(n+2)=5S(n+1)-3S(n)-S(n-1)

これを繰り返し使って S(11) を求めました。

    import sympy

    def solve(n):
        s = {1: sympy.fibonacci(3)}
        s[2] = s[1] + sympy.fibonacci(6)
        s[3] = s[2] + sympy.fibonacci(9)
    
        i = 4
        while sympy.fibonacci(3 * i) < n:
            s[i] = 5 * s[i - 1] - 3 * s[i - 2] - s[i - 3]
            i += 1
        return s[i-1]
        
    if __name__ == "__main__":
        nmx = 4 * 10 ** 6
        print(solve(nmx))