Ian Dorian Macleod
Problem 2
Problem Statement

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.

Approach

Computing Fibonacci numbers is a classic question in computer science. One of the first ways that many people approach the problem is with a recursive solution. This solution seems like the logical choice at first: after all, we have a clear base case ($F_0$ and $F_1$ are both equal to 1), and we can compute any nth number in the sequence as $$F_n = F_{n-1} + F_{n-2} \implies F_n = (F_{n-2} + F_{n-3}) + (F_{n-3} + F_{n-4}) \implies ...$$ This solution is computable for small numbers in the Fibonacci sequence, but its time complexity is $\mathcal{O}(n!)$, which is not polynomial by any stretch of the imagination and will quickly cause your computer to crash if you're not careful. The implementation that is used below is a variation on the last strategy that is (technically speaking) the first foray into dynamic programming in Project Euler. The idea is that we can store the last two values of the Fibonacci sequence and use those two values to compute the next value. After that, we just need to remember to update our values accordingly, so that the current value becomes the last value and the last value becomes the second to last value.

C++ implementation

#include <stdc++.h>
using namespace std;

int evenFib(int n) {
int sum = 0;
int prev = 1;
int prev_prev = 1;
int curr = 0;
while(curr < 4000000) {
curr = prev + prev_prev;
prev_prev = prev;
prev = curr;
if (curr % 2 == 0) res += curr;
}
return sum;
}

int main() {
cout << evenFib(400000) << endl;
return 0;
}

You can also download the source code for this problem here and compile it on your local machine.
Further Analysis

If this code doesn't make sense to you yet, I highly recommend writing out the sequence for small values of $n$ (try $F_5$) and following the code on paper to make sure that the value you get by hand is the same one that the code returns.