Project Euler

A Taste of Number Theory

Problem 2: Even Fibonacci Numbers

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 Catch

How to efficiently generate a Fibonacci sequence.
How to pick out the even-valued Fibonacci number.

The Light

The recursive approach to generating a Fibonacci sequence (time complexity of O(2n)) might not be as elegant as an iterative one. Consider this piece of code, which prints all Fibonacci numbers under 10 using the iterative approach (time complexity of O(n)). For every fibonacciNumber created, check if it is divisible by 2 to pick out the even-valued ones. Sum them up to find the answer.

int firstNumber = 1;
int secondNumber = 2;
int fibonacciNumber = 0;

System.out.print(firstNumber + " " + secondNumber);
while(fibonacciNumber < 10)
{
  fibonacciNumber = firstNumber + secondNumber;
  System.out.print(" " + fibonacciNumber);
  firstNumber = secondNumber;
  secondNumber = fibonacciNumber;
}

The Code

public class Problem2
{
  public static void main(String[] args)
  {
    fib(); 
  }

  public static void fib()
  {
    int f1 = 1;
    int f2 = 1;
    int fib = 0;
    int sum = 0;

    while(fib < 4000000)
    {
      fib = f1 + f2;
      if(fib % 2 == 0)
        sum += fib;

      f1 = f2;
      f2 = fib;
    }
    System.out.println(sum);
  }
}