Project Euler – Problem 2

So, here’s my take on the next Project Euler problem.

Problem 2 is indicated as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The first we can try is an obvious solution – try to go over every number in the Fibonacci sequence, check if it’s even valued, and add it to the accumulator if it is.

$sum = 0
$x = $y = 1
$limit = 4000000
while ($y -lt $limit) 
{
    if ($($y % 2) -eq 0)
    {
        $sum += $y
    } 
    $z = $x + $y
    $x = $y
    $y = $z
}

The solution goes in a loop through all Fibonacci sequence terms until the terms value goes over 4,000,000. In this solution variable $x holds the last sequence term (the n-1th one), variable $y holds the current sequence term (the nth one), and the variable $z is temporary, used to calculate the next term in the sequence (the n+1th one). The if statement checks if the current term is even, and if it is, the value is added to the accumulator $sum. After breaking from the loop, $sum holds the required answer.

However, checking every term to be even is not necessary – if you would write a long enough sequence, you would notice that every third term is even:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

So, it is possible to get to the required answer without checking if the value is even.

So, we can adjust the code to

$sum = 0
$x = $y = 1
$z = $x + $y
$limit = 4000000
while ($z -lt $limit)
{
    $sum += $z
    $x = $y + $z
    $y = $z + $x
    $z = $x + $y
}

and after the code runs, accumulator $sum holds the required answer.

So, what is going on in the code? Lets start from the beginning. Before the while loop starts, we calculate the first three terms in the sequence: 1, 1, 2. Because we know that the third term in the sequence is even, we add it to the accumulator. Next, we need to calculate the next three terms to get to the even valued one. So, we use

$x = $y + $z

to calculate the fourth term (that is, we add the second term $y to the third term $z and get the fourth term, which we assign to variable $x. Then, we calculate the fifth term using

$y = $z + $x

(as before, we add the third term $z to the fourth term $x and get the fifth term, which we assign to variable $y). And now, when we have both the fourth and the fifth terms, we can calculate the sixth term

$z = $x + $y

and assign it to variable $z.

Now we get the sequence 1, 1, 2, 3, 5, 8. The while loop starts over and treats the variables $x, $y, $z as if they were the first three terms in the sequence. We check for the value not going over the limit, and if it’s not we continue to execute the while loop. Applying the same logic that we outlined above, we add $z to the accumulator $sum and calculate the next three terms in the Fibonacci sequence.

Hope this was as interesting to read as it was writing it. Good luck implementing your own solutions! 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *