4000000以下のフィボナッチ数列の偶数項の総和

Project Euler 2

フィボナッチ数列の項は、直前の2項の和で表される。1, 2 から始まる場合、最初の10項は \[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ･･･\] となる。
このとき、フィボナッチ数列の項の値が4000000以下である偶数項の総和を求めよ。

---

フィボナッチ数列をそのままコード化すると、以下の通りとなる。

# SAMPLE_1

N = 4000000
fib_x1 = 1
fib_x2 = 2
ans = 0

fib = fib_x2
while(fib <= N):
    if fib % 2 == 0:
        ans += fib
    fib = fib_x1 + fib_x2
    fib_x1 = fib_x2
    fib_x2 = fib
print ans

偶数は奇数+奇数であり、奇数+奇数および奇数+偶数は奇数となる。
すなわち、フィボナッチ数列の偶奇性は、奇数である1と偶数である2からスタートし \[奇数, 偶数, 奇数, 奇数, 偶数, 奇数, 奇数, 偶数, 奇数, 奇数, ･･･\] となり、偶数は上記数列の第 2+3n 項(n=0,1,2･･･）に現れる。

さて、フィボナッチ数列の一般項は以下の式で表すことができる。 \[F(n) = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}} 　　ただし\ \phi = \frac{1+\sqrt{5}}{2}\] この式を用いて、偶数項のみを計算するコードは以下の通りとなる。
ただし、上記式で生成される数列は、1, 1, 2, 3, 5, ･･･ となり、問いの数列と異なるため、n の補正をする必要がある。

# SAMPLE_2
N = 4000000
S = 2
M = 3


def F(n):
    n += 1  # n を補正
    phi = (1 + sqrt(5)) / 2
    x = (pow(phi, n) - pow(1 - phi, n)) / sqrt(5)
    return int(x)

c = S
ans = 0
fib = F(c)

while(fib <= N):
    ans += fib
    c += M
    fib = F(c)
print ans