Project Euler/2

Project 2 on Project Euler: https://projecteuler.net/problem=2

Solution: https://git.charlesreid1.com/cs/euler/src/master/002

Sum of even Fibonacci numbers smaller than 4 million.

Note that this does not mean the even-number-indexed Fibonacci numbers 2, 4, 6, etc., but actually the Fibonacci numbers that are themselves even.

The solution

This is an interesting problem because it requires generating a very large number of Fibonacci numbers.

Ironically, because most computer science courses introduce recursion using the example of Fibonacci, and how tremendously inefficient it is to implement recursively, when you ask a programmer to implement the Fibonacci sequence, they typically implement a recursive version.

There are a couple of ways to do it more efficiently, the most obvious being a for loop or a while loop. I used a while loop.

		//Integer MAX = 10;
		Integer SUM = 0;

		// Fencepost
		Integer F_km2 = 1; // k = 1
		Integer F_km1 = 2; // k = 2
		Integer F_k = 3;
		Integer k = 3;

		SUM += 2; // <-- this was the trick to the problem.

		while(F_k < MAX) { // <-- make sure less than 4 million
			k++;
			F_km2 = F_km1;
			F_km1 = F_k;
			F_k = F_km2 + F_km1;

			if(F_k%2==0) { 
				SUM += F_k;
			}
		}

The generalization

A function to compute very large Fibonacci numbers is useful to have. 4 million does not push the number past normal 32-bit representations, but it's a good exercise to implement this using the BigInteeger type in Java or some other big number library.