Project Euler 2: Even Fibonacci Numbers

Problem

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.

Official Problem

Solution Approach

In this problem of even Fibonacci Numbers, we have to do a sum of even Fibonacci series. Let’s find a general approach first for solving this problem then let’s dive down to the more specific limiter like up to 4 million as asked in the question.

The problem can be approached in 2 ways – one can be a normal brute force technique which is generally used to find the Fibonacci series and secondly is the intelligent even Fibonacci sum by finding patterns and utilizing those patterns to perform the same.

Brute Force Approach

Let’s start with the brute force approach where we will set the first 2 numbers of the sequence as 1,2 as stated in the problem and find the third Fibonacci sequence by using the formula Fn = Fn-1 + Fn-2 so the next few terms in the series will be 3,5,8,13 and so on. We check all the numbers if they are even, which is generated through this formula, and calculate their sum.

Coming to the code part of this approach first declare initialize the sum as 0 then have another variable to store the nth value which is 4 million in our problem at hand. Set the nth term as an exit condition to the loop and iterate using the Fibonacci formula and generate the numbers. Also, keep checking if the number is even, and if it is so then add the number to the sum.

Optimized Approach

Now, moving to the more optimized answer to the problem we will first let’s see the series. We have

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

From the trend we can clearly see that every third character is an even number. We will use this information to solve the problem in hand

Now lets derive a relation of getting Fibonacci relation only between the even numbers.

If Fn is the nth Fibonacci number then Fn-1 and Fn-2 are the numbers before that. So we need to have a relation between Fn, Fn-3, and Fn-6 as even the Fibonacci number occurs as every 3rd Fibonacci number.

To derive the relation we already know that

Fn= Fn-1 + Fn-2

Fn = Fn-2 + Fn-3 + Fn-3 + Fn-4 (expanding Fn-1 = Fn-2 + Fn-3 and Fn-2 = Fn-3 + Fn-4)

Fn = Fn-3 + Fn-4 + 2Fn-3 + Fn-5 + Fn-6 (using the same logic we expand Fn-4 and Fn-2)

Fn = 4Fn-3 + Fn-6 (as Fn-4 + Fn-5 = Fn-3)

we can change it to EFn = 4EFn-1 + EFn-2 where EFn are even Fibonacci numbers.

Coming to the code part of this approach we initialize the sum variable to have a value of 0 and the limit variable to contain the value of 4 million. We already know the first 2 even numbers are 2 and 8 using the above formula we calculate the next terms by looping until the limit and we have to keep adding the numbers obtained from the formula to the sum variable. In the end, we will just print the sum variable’s value as the answer.

Solution Code

Brute Force Approach

Python Solution

sum = 0

limit = 4000000
Fn1 = 1
Fn2 = 2
Fn = 0

if(Fn1 % 2 == 0):
	sum += Fn1


if(Fn2 % 2 == 0):
	sum += Fn2


while(Fn <= limit):
	if(Fn % 2 == 0):
		sum += Fn
	
	Fn = Fn1 + Fn2
	Fn1 = Fn2
	Fn2 = Fn

print(sum)

sum = 0

limit = 4000000

Fn1 = 1

Fn2 = 2

Fn = 0

if(Fn1 % 2 == 0):

sum += Fn1

if(Fn2 % 2 == 0):

sum += Fn2

while(Fn <= limit):

if(Fn % 2 == 0):

sum += Fn

Fn = Fn1 + Fn2

Fn1 = Fn2

Fn2 = Fn

print(sum)

Java Solution

class Solution{
  public static void main(String[] args) {			
		int limit = 4000000;
		int fn1 = 1, fn2 = 2;
		int fn = 0;
		int sum = 0;

		if(fn1 % 2 == 0) sum += fn1;
		if(fn2 % 2 == 0) sum += fn2;

		while (fn < limit){
			if(fn%2==0) sum += fn;
			fn = fn1 + fn2;
			fn1 = fn2;
			fn2 = fn;
		}
		
		System.out.println(sum);
  }
}

class Solution{

public static void main(String[] args) {

int limit = 4000000;

int fn1 = 1, fn2 = 2;

int fn = 0;

int sum = 0;

if(fn1 % 2 == 0) sum += fn1;

if(fn2 % 2 == 0) sum += fn2;

while (fn < limit){

if(fn%2==0) sum += fn;

fn = fn1 + fn2;

fn1 = fn2;

fn2 = fn;

}

System.out.println(sum);

}

Optimized Approach

Python Solution

sum = 0

limit = 4000000
Fn1 = 2
Fn2 = 8
Fn = 0

if(Fn1 % 2 == 0):
	sum += Fn1

if(Fn2 % 2 == 0):
	sum += Fn2

while(Fn <= limit):
	sum += Fn
	Fn = 4*Fn2 + Fn1
	Fn1 = Fn2
	Fn2 = Fn

print(sum)

sum = 0

limit = 4000000

Fn1 = 2

Fn2 = 8

Fn = 0

if(Fn1 % 2 == 0):

sum += Fn1

if(Fn2 % 2 == 0):

sum += Fn2

while(Fn <= limit):

sum += Fn

Fn = 4*Fn2 + Fn1

Fn1 = Fn2

Fn2 = Fn

print(sum)

Java Solution

class Solution{
  public static void main(String[] args) {			
		int limit = 4000000;
		int fn1 = 2, fn2 = 8;
		int fn = 0;
		int sum = 0;

		sum += fn1;
		sum += fn2;

		while (fn < limit){
			sum += fn;
			fn = fn1 + 4*fn2;
			fn1 = fn2;
			fn2 = fn;
		}
		
		System.out.println(sum);
  }
}

class Solution{

public static void main(String[] args) {

int limit = 4000000;

int fn1 = 2, fn2 = 8;

int fn = 0;

int sum = 0;

sum += fn1;

sum += fn2;

while (fn < limit){

sum += fn;

fn = fn1 + 4*fn2;

fn1 = fn2;

fn2 = fn;

}

System.out.println(sum);

}

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂

Problem

Solution Approach

Brute Force Approach

Optimized Approach

Solution Code

Brute Force Approach

Python Solution

Java Solution

Optimized Approach

Python Solution

Java Solution

Leave a Comment Cancel Reply