# Problem 2

Problem: Find the sum of all the even numbers in the Fibonacci sequence whose values do not exceed 4 million.

Q: What is the minimum section of the sequence that we need to keep in memory at any one time?
A: 3 elements – current element and previous two elements (which are used to calculate the current element).

Q: What is the starting point?
A: 1, 1, 2 (the first three elements).

Q: What is the rule to update the elements?
A: Remove element 0, push elements 1 and 2 back one space, recalculate the new element 2 as the sum of elements 0 and 1.

Memory requirements: 3 x 32 bit integers (sufficient to hold a value of 4 million) and 1 x 64 bit integer for the sum of all even elements.

Solution:

```#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define MAX_SEQUENCE 4000000

int main(void)
{
// Fibonnaci sequence actually starts 1, 2 but pretending it is 1, 1, 2 allows
// us to use the same logic for every step instead of treating the first one
// as a special case
uint32_t sequence[] = {1, 1, 2};
uint64_t sum = 0;

while (sequence <= MAX_SEQUENCE)
{
if (sequence % 2 == 0)
{
sum += sequence;
}

// Move all elements back one space, then recalculate current element
sequence = sequence;
sequence = sequence;
sequence = sequence + sequence;
}

printf("%" PRIu64 "\n", sum);

return EXIT_SUCCESS;
}```