Project Euler: 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 integers to hold the current element and the previous elements, and 1 integer for the sum of all even elements.

<?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");

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.