Sum of Even Fibonacci Numbers (Project Euler Problem 2)

Reading time: 30 minutes | Coding time: 5 minutes

In this problem, we want to find the sum of even fibonacci numbers that is fibonacci numbers that are even and is less than a given number N. We will present a couple of insightful ideas about this problem which will enable you to solve it efficiently.

With the ideas, you can solve the Problem 2 of Project Euler.

A fibonacci series is defined by:

F(N) = F(N-1) + F(N-2)

where F(1) = 1 and F(0) = 1

The key idea is that we can directly generate the even numbers and skip generating the odd numbers as even numbers follow the following equation (which we will prove):

E(N) = 4 * E(N-1) + E(N-2)

where E(0) = 2 and E(1) = 8

Brute force

The brute force approach is to generate all fibonacci numbers less than N and get the sum of numbers which are even.

Pseudocode:

find_sum(N)
{
    int one = 1;
    int two = 1;
    int temp = 0;
    int sum = 0;
    while(one < N)
    {
        if(one % 2 == 0)
            sum += one;
        temp = two;
        two = two + one;
        one = temp;
     }
     return sum;
}

Implementation:

class opengenus 
{
    static int find_sum(int N)
    {
        int one = 1;
        int two = 1;
        int temp = 0;
        int sum = 0;
        while(one < N)
        {
            if(one % 2 == 0)
                sum += one;
            temp = two;
            two = two + one;
            one = temp;
         }
         return sum;
    }

	public static void main (String[] args) 
	{
		int N = 1000;
		int sum = find_sum(N);
		System.out.println(sum);
	}
}

Output:

798

Efficient approach

We can improve the above algorithm by making some critical observations. First observation is that every third number in the Fibonacci series is even. Other numbers are odd.

See:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

This is because we can get an even number only if we add two even numbers or two odd numbers. Two consecutive even numbers cannot exist as we are starting with two odd numbers so the only case to generate an even number is through the sum of two odd numbers.

For this to happen, we will observe that only the third number can be even as from an even number, we need two steps to generate two consecutive odd numbers.

The key observation is that we need not generate other fibonacci numbers as we can generate the even numbers directly using the following recursive method:

E(N) = 4 * E(N-1) + E(N-2)

where E(0) = 2 and E(1) = 8

We will prove this using the original Fibonacci relation which is:

F(N) = F(N-1) + F(N-2)

Note that we need only the third numbers. So, our focus is to generate F(N) using F(N-3) and F(N-6) as both of these will be even and following it F(N) will be even as well.

The proof is as follows:

F(N) = F(N-1) + F(N-2)
     = F(N-2) + F(N-3) + F(N-2)
     = 2 * F(N-2) + F(N-3)
     = 2 * (F(N-3) + F(N-4)) + F(N-3)
     = 2 * F(N-4) + 3 * F(N-3)
     = F(N-4) + F(N-5) + F(N-6) + 3 * F(N-3)
     = F(N-3) + F(N-6) + 3 * F(N-3)
     = 4 * F(N-3) + F(N-6)

Hence, if we generate the elements of this sequence and add the numbers, we will solve this problem efficiently. Note that the complexity of the algorithm remains the same but we have reduce the number of computations by a factor of 3 which is great in terms of performance.

Pseudocode:

find_sum(N)
{
    int one = 2;
    int two = 8;
    int temp = 0;
    int sum = 0;
    while(one < N)
    {
        sum += one;
        temp = two;
        two = 4 * two + one;
        one = temp;
     }
     return sum;
}

Implementation in Java:

class opengenus 
{
    static int find_sum(int N)
    {
        int one = 2;
        int two = 8;
        int temp = 0;
        int sum = 0;
        while(one < N)
        {
            sum += one;
            temp = two;
            two = 4 * two + one;
            one = temp;
         }
         return sum;
    }

	public static void main (String[] args) 
	{
		int N = 1000;
		int sum = find_sum(N);
		System.out.println(sum);
	}
}

Output:

798

With this, you have the complete knowledge of solving this problem.