Project Euler Problem #2

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.

Solution:

As always, it helps to restate the problem. We want to find the sum of all even Fibonacci numbers less than or equal to four million. The general formula for Fibonacci numbers is:
F_i = F_i-2 + F_i−1

Breaking it down, we have two sub-problems:

Generate the sequence of even Fibonacci numbers less than or equal to four million.
Find their sum.

There's a recursive solution that is initially tempting

def fibonacci(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n-2) + fib(n-1)

However, don't be so hasty. Expanding out this solution reveals that its time complexity is completely unacceptable. For example, if we wanted to the calculate fibonacci(8), this function would perform the following work:

fibonacci(8) = fibonacci(6) + fibonacci(7)
fibonacci(7) = fibonacci(5) + fibonacci(6)
fibonacci(6) = fibonacci(4) + fibonacci(5)
fibonacci(5) = fibonacci(3) + fibonacci(4)
fibonacci(4) = fibonacci(2) + fibonacci(3)
fibonacci(3) = fibonacci(1) + fibonacci(2)
fibonacci(2) = fibonacci(0) + fibonacci(1)
fibonacci(1) = 1

For each non-base case call, we perform two recursive calls. The first call produces 2 calls, which each produce 2 more calls, making 4. Each of those produce 2 more calls, making 8. Once we're k levels down, that's 2^k non-recursive calls. Exponential growth. Yikes. Even worse, notice how we calculate values like fibonacci(5) and fibonacci(4) multiple times? We're not even doing useful exponential work, but just recalculating the same values over and over again.

If you're dead-set on recursive solutions and know a thing or two about computer science, you'll know that this is a classic dynamic programming problem. We could trade off time for space complexity using memoization to avoid recalculating values. But I hate recursion and don't know much about dynamic programming, so screw that.

Every recursion can be re-written as an iteration. To generate all Fibonacci numbers less than n, it looks something like this:

a, b = 0, 1
while a < n:
  print(a)
  a, b = b, a+b

# For n = 500, we get the following output
# 0
# 1
# 1
# 2
# 3
# 5
# 8
# 13
# 21
# 34
# 55
# 89
# 144
# 233
# 377

# To make it only print even, we simply modify it like so:
a, b = 0, 1
while a < n:
  if a % 2 == 0:
    print(a)
  a, b = b, a+b

That's basically the entire problem. All we have to do to turn this into a solution is replace print with a running total and wrap it in a neat little bow.

def calculate_fibonacci_sum(n):
    total = 0
    a, b = 0, 1
    while a < n:
        if (a % 2 == 0):
            total += a
        a, b = b, a + b
    return total

Better yet, this implementation improves on our exponential recursive solution by only looping through Fibonacci numbers instead of recalculating them repeatedly. Because Fibonacci numbers grow exponentially, we only need a few steps to reach n. Instead of checking every number up to n, we skip ahead quickly, reducing the number of iterations to about log(n). The time complexity of this solution is O(log(n)) and it's space complexity is O(1).

Addenda & Future Expansion

Implementation of dynamic programming solution.
Using basic proofs, we can show that the Fibonacci sequence actually follows a defined pattern of odd and even numbers.
- Even + Even = Even
  An even number is any integer divisible by 2 e.g. 2n for an integer n. The above statement is true because 2n + 2m = 2(n + m) for any two integers n and m. The sum of any two integers is another integer k, making this equal to 2k and therefore even.
- Odd + Odd = Even
  The formula for an odd number is 2n-1. For any two integers n and m, this would be 2n-1 + 2m-1 = 2n + 2m - 2 = 2(n + m - 1). Hence, an even number.
- Odd + Even = Odd
  2n + 2m-1 = 2(n + m) - 1. The sum of any two integers n and m is an integer k, making this equivalent to 2k-1, hence odd.
- Starting at 0 and 1, we have even and odd. Adding them together gives us 1, an odd number. The sequence so far is thus
  even, odd, odd
- Adding 1 + 1 is 2, therefore even. 1 + 2 is 3, odd. 2 + 3 is 5, odd.
  even, odd, odd, even, odd, odd
  See the pattern?
- If we look at the original example given by Project Euler starting at 1 and 2, we see a similar pattern
  odd, even, odd, odd, even, odd, odd, even, odd, odd
  Adding another 1 to the beginning doesn't break the sequence and completes the pattern. Write another solution that takes advantage of this.

Project Euler Problem #2

Problem Statement:

Solution:

Addenda & Future Expansion