Project Euler Problem 2 – Fibonacci sequence

Solving the Project Euler Problem 2 is simple and I believe it still does not required great processing power to search for the clever algorithms. The description of Problem 2 is:

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

In the order to find a final sum, first it is necessary to generate the Fibonacci sequence. The sum of the first 2 elements in the sequence creates the third. The loop than go on and the second and the third element create forth , etc.

All we need to do now do is just to check if the newly generated number is dividable by 2. If it is we can sum it up with the rest. The sum is already 2 since we begin by generating the 3rd number (the sum of first 2 elements $a and $b).

So the algorithms goes like this:

  1. Definition of starting variables.
  2. Loop for generating +1 bigger number.
  3. Check if number is dividable by 2.
  4. If yes, number is summed.
  5. Output of result.

PHP:

<?php 
$sum = 2;
$a = 1;
$b = 2;
$c = null;
while ($c < 4000000) {
	$c = $a + $b;
	if($c%2 == 0) {
		$sum += $c;
	}
	$a = $b;
	$b = $c;
}
echo $sum;
?>

Java:

public class Project_Euler_Problem_002 {
	public static void main(String[] args) {
		
		System.out.println("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:");
		System.out.println("1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …");
		System.out.println("Find the sum of all the even-valued terms in the sequence which do not exceed four million.");

		int sum = 2, a = 1, b = 2, c = 0;
		while (c < 4000000) {
			c = a + b;
			if(c%2 == 0) {
				sum += c;
			}
			a = b;
			b = c;
		}
		
		System.out.println("\n"+ "Sum is: " + sum);;
	}
}

Hint:  While reviewing the algorithm with the solutions of others I notice a difference. This algorithm is based on the Fibonacci sequence starting 1,2,3… not 1,1,2,3.

This entry was posted in Computer Science. Bookmark the permalink.

1 Response to Project Euler Problem 2 – Fibonacci sequence

  1. Pingback: Project Euler Problem 3 - Largest prime factor - CodeKopf.com

Leave a Reply

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

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