10
\$\begingroup\$

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

  1. Give me all Fibonacci numbers up to 4000000

  2. Give the sum of all even numbers up to 4000000

  3. It satisfies Project Euler Question #2.

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

\$\endgroup\$
11
\$\begingroup\$

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:

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

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Upvoted for interesting mathematical observations, even though it's not exactly a code review. In practice, applying the O(1) formula is not that easy, and the "brute-force" approach might be faster once you consider the ease of implementation vs. the trivial amount of computation involved. \$\endgroup\$ – 200_success Nov 19 '13 at 11:09
  • 1
    \$\begingroup\$ @200_success you raise an interesting point -- in my opinion, discussions about the underlying algorithm and its impact on performance are part of a code review. However, the about pages are a bit vague on this. Could anyone clarify? \$\endgroup\$ – publysher Nov 19 '13 at 12:44
  • 1
    \$\begingroup\$ I take that back about "not exactly a code review". "You used the wrong algorithm because …" is perfectly fair as a review. It's just that I disagree that your suggested O(1) solution would result in better code. \$\endgroup\$ – 200_success Nov 19 '13 at 15:47
  • 1
    \$\begingroup\$ Point taken, and I agree that the O(1) solution is not necessarily more readable; probably not. I do feel that this solution is more in the spirit of project Euler :) \$\endgroup\$ – publysher Nov 20 '13 at 11:10
7
\$\begingroup\$

More elegantly, using a generator:

def fib(max):
    f1, f2 = 0, 1
    while f1 < max:
        yield f1
        f1, f2 = f2, f1 + f2

print(sum(filter(lambda n: n % 2 == 0, fib(4000000))))

I would consider this to be more elegant because it decomposes the problem into describable, reusable components, instead of mingling all the logic together:

  • The fib() generator is responsible for generating Fibonacci numbers
  • filter(lambda n: n % 2 == 0, ...) keeps just the even-valued elements
  • sum(...) adds them up
\$\endgroup\$
1
\$\begingroup\$

Assuming you want to stick with a minimalist for-loop implementation, it could be simplified by using Python's simultaneous assignment feature to eliminate a variable and perform the "swap" gracefully. Of course, the question does not require you to produce the even-valued items of the Fibonacci sequence, so you could eliminate debugP2 as well.

sum = 0
f1, f2 = 0, 1
while f2 < 4000000:
    if f2 % 2 == 0:
        sum += f2
    f1, f2 = f2, f1 + f2
print(sum)
\$\endgroup\$

protected by Jamal Apr 11 '16 at 10:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.