Project Euler Question #2: Sum of even Fibonacci numbers under 4 million

The question is:


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, ...


By considering the terms in the Fibonacci sequence whose values do not exceed four
million, find the sum of the even-valued terms.

#Problem 2
P2 = 0
fib= 0
f1 = 1
f2 = 0
debugP2 = []
while fib < 4000000:
    fib = f1 + f2
    f2 = f1
    f1 = fib
    if fib % 2 == 0:
        P2 += fib
        debugP2.append(fib)
print(debugP2)
print(P2)

This script can

-
Give me all Fibonacci numbers up to 4000000

-
Give the sum of all even numbers up to 4000000

-
It satisfies Project Euler Question #2.

Is there a way to make this shorter or more efficient?

Your current implementation, and the suggested improvements are all brute force implementations, i.e. enumerating all fibonacci numbers, and they will all run in O(n).

By using some mathematical tricks, you can turn this into an O(1) implementation. Since this is a project Euler problem, I won't spell out the answer, but here are some pointers:

-
When starting at F(0) = 1 (instead of starting at F(1) as in the problem description), every third number is an even fibonacci number

-
Because the fibonacci numbers are by definition based on the addition of the previous two numbers, the sum of all even fibonacci numbers up to n is equal to the sum of all fibonacci numbers up to n divided by two.

-
There are cool formula's to calculate the sum of fibonacci numbers and the index of the highest fibonacci number up to n. Refer to wolframalpha or wikipedia to find them.

StackExchange Code Review Q#35322, answer score: 12