Tags

, , ,

The second Project Euler problem isn’t much more difficult than the first. The problem goes thusly:

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.

The solution is pretty straightforward: count up the Fibonacci numbers from 1 to 4,000,000, check for even ones, and add them up along the way.

Here it is in C++:

#include <iostream>
using namespace std;

int main()
{
     int a = 1, b = 2, fib = 0, answer = 2;
     while (a+b < 4000000){
          fib = a+b;
          if (fib % 2 == 0) {answer += fib;}
          a = b;
          b = fib;
     }
     cout << endl << "The sum of the even Fibonacci numbers less than 4,000,000 is " << answer << endl;
     return 0;
}

The algorithm rests on two ideas:

  1. We will always keep track of four numbers: the rolling sum which will ultimately be the answer when the loop terminates (answer), the current Fibonacci number (fib) and the previous two (a, b).
  2. We will use a while loop to control our iteration, exiting before we reach 4,000,000.

I started at the first even Fibonacci number (answer = 2), and added up from there. The loop checks to see if the next number in sequence will exceed 4,000,000, and then executes. Inside the loop, we just calculate the next number in the sequence, check to see if it’s even, add it to our rolling sum if it is, then increment a and b so that we’re ready for the next iteration of the loop. When we reach a point where the next Fibonacci number would exceed 4,000,000, we exit the loop before we get to it.

I left in a debugging line (cout << fib << endl;), because it is fascinating to me how fast we reach 4,000,000.

Here is the same algorithm in Python:

a = 1
b = 2
fib = 0
answer = 2

while (a+b < 4000000):
    fib = a+b
    if (fib%2==0):
        answer += fib
    a = b
    b = fib
    print fib

print "The sum of the even Fibonacci numbers less than 4,000,000 is " + str(answer)
Advertisements