# Problem 2

## Problem

Find the sum of the even Fibonacci numbers up to 4 million.

## General solution

Given the small search space, the simplest solution is to calculate the next Fibonacci number and check if it is even, and if so add it to the running total.

Although the list of Fibonacci numbers up to 4 million is long, we only need to keep the previous two numbers in memory, as that is sufficient to calculate the next number. This can be achieved with an array of three elements:

- Previous number (1)
- Previous number (2)
- Current number (sum of the previous two)

Each time we need a new number, we move the existing elements back one place (the first one will effectively drop out of the array) and recalculate the current number.

The only setup required is to prime the array with the first 3 numbers, which are: 1, 1, 2.

## Solution: Go

Go does not have a `while`

loop but we can simulate one with a `for`

loop with no initialiser or step.

```
package main
import (
"fmt"
)
const MAX_SEQUENCE = 4000000
func main() {
sum := 0
sequence := [3]int{1, 1, 2}
for ; sequence[2] <= MAX_SEQUENCE; {
if sequence[2] % 2 == 0 {
sum += sequence[2]
}
// Move all elements back one space, then recalculate current element
sequence[0] = sequence[1]
sequence[1] = sequence[2]
sequence[2] = sequence[0] + sequence[1]
}
fmt.Println(sum)
}
```

## Solution: PHP

```
<?php
declare(strict_types=1);
error_reporting(E_ALL);
define('MAX_SEQUENCE', 4000000);
// 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
$sequence = [1, 1, 2];
$sum = 0;
while ($sequence[2] <= MAX_SEQUENCE)
{
if ($sequence[2] % 2 === 0)
{
$sum += $sequence[2];
}
// Move all elements back one space, then recalculate current element
$sequence[0] = $sequence[1];
$sequence[1] = $sequence[2];
$sequence[2] = $sequence[0] + $sequence[1];
}
print("$sum\n");
```

## Solution: C

```
#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[2] <= MAX_SEQUENCE)
{
if (sequence[2] % 2 == 0)
{
sum += sequence[2];
}
// Move all elements back one space, then recalculate current element
sequence[0] = sequence[1];
sequence[1] = sequence[2];
sequence[2] = sequence[0] + sequence[1];
}
printf("%" PRIu64 "\n", sum);
return EXIT_SUCCESS;
}
```