Sum of Even Fibonacci numbers till four million – Project Euler Problem 2

As promised, today I am posting the solution of second problem presented in Project Euler, you can find other solved problems here

Problem statement:

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.

Solution:


public class EulerEvenFibonaccinumbers{

public static void main(String args[]){

long evenSum=0;

long fibo1=1, fibo2=1, fibonacci=1;

for(long i= 3; i<= 150; i++){

if(fibonacci>=4000000)

break;

fibonacci = fibo1 + fibo2;

fibo1 = fibo2;

fibo2 = fibonacci;


if(fibonacci%2==0){

evenSum=evenSum+fibonacci;

}

}


System.out.println(evenSum);



}

}

It is a very simple program, first you need to write a loop from 3 to 150(It was my guess that we would get Fibonacci term greater than 4 million with in 150 iterations, but that too is way too much, you can get actual result at iteration number 34 ).

but why from 3?

Because first two numbers in Fibonacci series are obvious i-e 1,1 and they both are not needed in final sum as 1 is not an even number, so we have started from 3rd iteration.

In very first line of loop there is a check if the Fibonacci number is greater than or equals to four million, system will terminate the loop, as this is the requirement that Fibonacci term should not exceed from 4,000,000(This check is not needed if you run loop exactly from 3 to 34, as mentioned above desired result will be achieved at iteration number 34)

Following block of code is generating Fibonacci series by simply adding and swapping values of three variables fibonacci,fibo1 and fibo2

fibonacci = fibo1 + fibo2;

fibo1 = fibo2;

fibo2 = fibonacci; 

First line is adding numbers then on second line second number ‘fibo2’ is assigned to first variable ‘fibo1’ and the sum of two numbers ‘fibonacci’ is assigned to second variable ‘fibo2’.

Then on next iteration fibo2 will have the new number and fibo1 have the number previously assigned to fibo2.

lets dry run it for better understanding.

First Iteration:

fibo1=1

fibo2=1

fibonacci=fibo1+fibo2 which makes

fibonacci=2

then fibo1=fibo2 which will be

fibo1= 1

and fibo2= fibonacci which means

fibo2= 2

Second Iteration:

fibo1=1

fibo2=2

fibonacci= fibo1+fibo2

fibonacci=3

fibo1=2

fibo2=3

and so on till fibonacci = > 4,000,000

In each iteration ‘fibonacci’ is also checked if it is even or odd by checking its remainder after dividing it to 2

if(fibonacci%2==0){

evenSum=evenSum+fibonacci;

If ‘fibonacci’ is even that is, if its remainder is 0 after dividing it to 2, then ‘fibonacci’ will be added to ‘evensum’ , which actually holds our final result: The sum of even fibonacci numbers.

Final Result:

Final result is 4613732

Advertisements

2 thoughts on “Sum of Even Fibonacci numbers till four million – Project Euler Problem 2

  1. Nice and easy to understand, but why do you need both the limiting loop to 150 and the condition of 4 million? Surely you only need the stopping condition of 4 million since this was the problem. To get to an answer of 34 loops you actually had to run the code. Surely the number of loops is not improving any part of this code?

    Like

    • wwalford, Thank you. I put both just to clear both scenarios. yes, surely we don’t need 4 million check if we implement limit 34 to the loop but as you yourself already mentioned I first had to run the code to get actual number of iterations need to be implemented. So, first I implemented loop with 150 limit and condition of 4 million.Then, once I got actual number of iterations needed to get actual result I removed the condition and limited number of iterations to 34. But mentioned both just to make every thing clear to the reader. Cheers!! 🙂

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s