HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Sum of even Fibonacci numbers

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
evennumbersfibonaccisum

Problem

So, in my first attempt I created a code that generated all fibonacci numbers and appended to a list. This list I then traversed to get the even numbers and added them up. It worked, but took like 5 complete seconds to work.
Then I decided to not create a list and add the even numbers as I'm generating them. It looked like this

a = 1
b = 1
c = 0
Sum = 0
while c<4000000:
    c = a + b
    if c%2==0:
        Sum+=c
    a = b
    b = c
print Sum


It still took quite a lot of time (didn't record it) compared to the people who got it done in like 100 milliseconds or something (I got this question on Project Euler).
Is there a way to make it faster?
Here's the link to the problem

https://projecteuler.net/problem=2

Solution

Obviously, every third Fibonacci number is even, and the rest of them are odd. Less obviously (but trivially follows from, say, Binet's formula), they satisfy another linear recurrence:

\$F_{3(n+1)} = 4 F_{3n} + F_{3(n-1)}\$

Using this fact, you may cut the execution time threefold.

Context

StackExchange Code Review Q#140628, answer score: 5

Revisions (0)

No revisions yet.