Problem 2 - Even Fibonacci Numbers

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, 1, 2, 3, 5, 8, 13, 21, 34, 55, 99, ... $$

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

First things first, we will have to come up with an algorithm to generate Fibonacci numbers. With the help of the internet, below is the algorithm:

def fib(n):
  if n < 3:
    return 1
  counter = 3
  last1 = 1
  last2 = 1

  while counter <= n:
    result = last1 + last2
    last2 = last1
    last1 = result
    counter += 1
  return result

The gist of the algorithm is on line 9-11, a new variable called result is created, which stores the sum of the previous 2 numbers, and then continue the sum with the new result value. If that is still not obvious, perhaps the help of below image will be of use:


Imagine your finger is pointing to last1 and last2 variable and computing the result. After you got your answer, your finger now moves to last1 and result as the new (last2, last1) variable, and continue to calculate the result. This is repeated till the counter exceeds the parameter passed in, and result is returned.

Now, we need another algorithm to extract the even number from the Fibonacci sequence. The straightforward idea is then to generate each Fibonacci numbers, and check if it is equal. If yes, add it to the sum tally. The algorithm will keep looping, until the generated Fibonacci numbers exceeded the limit parameter:

def computeEvenFibSum(limit):
  i = 1
  sumTally = 0

  while True:
    currentFib = fib(i)
    if currentFib > limit:
      return sumTally
      break
    if currentFib % 2 == 0:
      sumTally += currentFib
    
    i += 1

In the example, it will check every number in the sequence, and determine \(2\), \(8\), \(34, ...\) and so on is the even number in the sequence, and sum them up to get the answer.

As always, can we do even better?

Optimization

By looking at the Fibonacci sequence, is there any observation you can made about the "oddness and evenness" of number?

There seems to be a sequence established, with $$\text{odd, even, odd, odd, even, odd, odd, even, ...}$$ The even number seems to always follow by a sequence of two consequtive odd numbers. This is due to a rule: odd + odd = even number. We will try to prove it in below.

---

Suppose we have two different odd numbers which have the definition \(2n+1\) and \(2m+1\), where \(n\) and \(m\) can be any integer. When summing them up:

$$\begin{split} (2n+1) + (2m+1) & = 2n+2m+2\\ & = 2(n+m+1) \end{split} $$

The resulting number \(2(n+m+1)\) has a factor of \(2\) and therefore divisible by it, making it a even number.

What about the sum of even and odd number?

$$\begin{split} (2n) + (2m+1) & = 2n+2m+1\\ & = 2(n+m)+1 \end{split} $$

The resulting number cannot be cleanly divided by \(2\), making it an odd number.

---

With this, it seems that every 3rd number of the Fibonacci sequence is even number. Thus we can improve on the algorithm by initialize the counter as 3, increment it by 3, and remove the even number checking:

def computeEvenFibSum_v2(limit):
  i = 3
  sumTally = 0
  
  while True:
    currentFib = fib(i)
    if currentFib > limit:
      return sumTally
      break
    else: 
      sumTally += currentFib
    
    i += 3

When checking with input \(400,000,000\) on both algorithms,

Input: 400000000
Sum: 350704366
--- 8.225440979003906e-05 seconds ---

Input: 400000000
Sum: 350704366
--- 1.6927719116210938e-05 seconds ---