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

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

A brute force method would be to iterate through all the Fibonacci numbers under four million, and for each test if the number is even, then add it to the sum if it is even. But if we look at the sequence of numbers, we can see a pattern of even numbers.

term 0 1 2 3 4 5 6 7 8 9 10 11 12
value 1 1 2 3 5 8 13 21 34 55 89 144

Every third Fibonacci number is even. If Fib(n) equals the value of the nth Fibonacci term, we can add every third term to find the answer.

Let's start with Fib(2). Fib(2) = Fib(1) + Fib(0). By definition, we know Fib(0) and Fib(1) both equal one, so Fib(2) equals two. To get the next even term, we need to add 3 to n: Fib(5) = Fib(4) + Fib(3). Ignoring the term/value table above, we can calculate Fib(3) because we know the values of Fib(2) and Fib(1). Then, we can calculate Fib(4) because we know the values of Fib(3) and Fib(2). And finally, we can calculate the value of Fib(5) because we know Fib(4) and Fib(3).

The solution in lisp:

(defun problem-2 (limit)
  (do* ((sum 0 (+ sum n))
           (n-2 1 (+ n-1 n))
           (n-1 1 (+ n n-2))
           (n 2 (+ n-2 n-1)))
       ((< limit n) sum)))

The '*' after the 'do' is necessary so the terms are evaluated in sequence rather than in parallel.

In python:

def problem2(limit):
 sum = 0
 n2, n1, n = 1, 1, 2
 while n < limit:
   sum += n
   n2 = n1 + n
   n1 = n2 + n
   n = n1 + n2
 print sum