Grind Report 2

Going after the next Euler problem.

Problem 2

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.

*WARNING: This contains the solution!*

Ah yes, the good ol' Fibonacci sequence. Back during my senior year in high school a good friend and myself decided one day to memorize the 100th term in the Fibonacci sequence (63 digits). Later we had a race to see who could write it faster on the whiteboard of our Calculus class. Good times~

If the 100th term is 63 digits long then I know that the solution will not even get close to the 100th term. This is good if I were to apply a brute force method to this. There is something called Binet's Formula which can be used to calculate a term. This is really cool but there are two problems with applying this to the actual problem.

1. We need to find the sum of the terms. Meaning we would still need to calculate most of the terms. Since a given term is the sum of the previous 2 terms, we would be able to skip every 2 terms and add the term twice. 1 + 5 (2) + 21 (2) + 89 (2)
2. As we can see (if you look at it) this formula is somewhat complicated in terms of calculations. Using this formula instead of a brute force method may actually be slower in code.
3. Adding another problem, which conflicts with the second half of #1. I nearly forgot that we are only adding even terms.

I believe it is pretty obvious that for this problem we want to use simple brute force considering all of these extra costs that are included in calculating a term using Binet's formula. I am going to use recursion.

#include <iostream>
using namespace std;

int const FIBCAP = 4000000;

int const FIB1 = 0;
int const FIB2 = 1;

int sumFibonacci(int previous1, int previous2)
{
   //calculate the next term
   int next = previous1 + previous2;
   //stops the recursion once the cap is met
   if (next > FIBCAP)
       return 0;
   //check to see if this term is even
   else if (next % 2 == 0)
       return sumFibonacci(previous2, next) + next;
   else
       return sumFibonacci(previous2, next);
}


int main()
{
   int answer = sumFibonacci(FIB1, FIB2);
   cout << "Answer: " << answer << endl;
    return 0;
}

This returned the correct solution the first time I ran it. However, once I got it right I was able to view the .pdf solution Project Euler provides and I see I failed to see that we can know when an even number occurs in the sequence. It is every 3rd number. This is a minor improvement but an improvement nonetheless. I was very close to catching this and would have if I had taken the time to write things down instead of doing everything in my head. Lesson learned.

*saved game*