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

http://projecteuler.net/problem=2

Brute Force

function euler2() {
  var sum = 0,
      fn = 1,
      fm = 1; // f n-1
  while (fn < 4000000) {
    if (fn % 2 === 0) {
      sum += fn;
    }
    fn = fn + fm;
    fm = fn - fm;
  }
  return sum;
}
timer(euler2, 100000);
// euler2 x 100000: 16.298ms
// 4613732

# Time O(n)

Patterns

Let’s take a look at the values of the sequence.

var n = 1,
    fn = 1,
    fm = 0; // f n-1
while (n < 25) {
  console.log('n', n, 'fib', fn, fn%2 === 0 ? 'even' : '');
  fn = fn + fm;
  fm = fn - fm;
  n++;
}

n 1 fib 1
n 2 fib 1
n 3 fib 2 even
n 4 fib 3
n 5 fib 5
n 6 fib 8 even
n 7 fib 13
n 8 fib 21
n 9 fib 34 even
n 10 fib 55
n 11 fib 89
n 12 fib 144 even
n 13 fib 233
n 14 fib 377
n 15 fib 610 even
n 16 fib 987
n 17 fib 1597
n 18 fib 2584 even
n 19 fib 4181
n 20 fib 6765
n 21 fib 10946 even
n 22 fib 17711
n 23 fib 28657
n 24 fib 46368 even

What we can see is that $F_3$, $F_6$, $F_9$, … $F_{(n\,multiple\,of\,3)}$ are the even fibonacci numbers.

Using this is a bit of information is going to take some manipulation. A fibonacci number can be generalized as:

$F_n = F_{n-1} + F_{n-2}$

Using $F_{n-1} = F_{n-2} + F_{n-3}$ to replace $F_{n-1}$ we get:

$F_n = (F_{n-2} + F_{n-3}) + F_{n-2} = 2F_{n-2} + F_{n-3}$

Using $F_{n-2} = F_{n-3} + F_{n-4}$ to replace $F_{n-2}$ we get:

$F_n = 2F_{n-3} + 2F_{n-4} + F_{n-3} = 3F_{n-3} + 2F_{n-4}$

Using $F_{n-4} = F_{n-5} + F_{n-6}$ to replace a single $F_{n-4}$ we get:

$F_n = 3F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6}$

Going the other way, replacing $F_{n-4} + F_{n-5}$ with $F_{n-3}$ we get:

$F_n = 3F_{n-3} + F_{n-3} + F_{n-6} = 4F_{n-3} + F_{n-6}$

For example:

$F_6 = 4F_3 + F_0 = 4\times2 + 0 = 8$

We can use this to solve our problem!

Better Brute Force

function euler2() {
  var sum = 0,
      fa = 2, // f n-3
      fb = 0; // f n-6
  while (fa < 4000000) {
    sum += fa;
    fa = 4*fa + fb;
    fb = (fa - fb) / 4;
  }
  return sum;
}
timer(euler2, 100000);
// euler2 x 100000: 8.252ms
// 4613732

# Time O(n)

We are using a trick to set the new value of the $F_{n-6}$ variable, fb. We want to set fb to $F_{n-3}$ , but the variable we were using for $F_{n-3}$ , fa has been set to $F_{n}$ . We can use our knowledge that $F_{n-3} = \frac{F_{n} - F_{n-6}}4$ and set fb to (fa - fb) / 4.