Output練習のためProjectEulerを解いてみる #2

Output練習のためProjectEulerを解いてみる第二問目です。
それでは解いていきます。

#2 Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be:
$$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

意訳

フィボナッチ数列$F_n$を以下の式で定義する。

F_n = F_{n-1} + F_{n-2} \;\;\;\; (n \geq 2)

$F_0 = 1, F_1 = 2$とすると、初めの10項は
$$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$
とあらわされる。
値が400万以下のフィボナッチ数列を考えたとき、偶数の値の総和を求めよ

方針

ひとまず定義通りにフィボナッチ数列を書き上げ、偶数の値を取り上げて足し上げてます

解法1

ProjectEuler_2.py

from functools import lru_cache

@lru_cache(maxsize=10000)
def Fibonacci(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

ans = 0
LIMIT = 4000000
n = 0
while Fibonacci(n) < LIMIT:
    print(n)
    if Fibonacci(n) % 2 == 0:
        ans += Fibonacci(n)
    n += 1
print(ans)

これを解くと4613732が得られる。

解法2

今回のフィボナッチ数列の偶奇を考えてみると、
$$奇,偶,奇,奇,偶,奇,奇,偶 \dots$$
となる。これの偶数の項数を見ると1,4,7と3つ飛びになっているので、それを再現すればよし

ProjectEuler_2.py

from functools import lru_cache

@lru_cache(maxsize=10000)
def Fibonacci(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

LIMIT = 4000000
n = 0
num = []

while Fibonacci(n) < LIMIT:
     num.append(Fibonacci(n))
     n += 1
print(sum(num[1::3]))