phpdev.uk: Project Euler

Problem 2

Posted on Nov 18, 2022

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:

  1. Previous number (1)
  2. Previous number (2)
  3. 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;
}