Problem #2 easy

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, \dots$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

View on Project Euler

Implementations

#include <iostream>
int main(int argc, char* argv[])
{
  unsigned long long sum = 0;
  unsigned long long a = 1, b = 2;
  while (b <= 4000000) {
    if (b % 2 == 0) {
      sum += b;
    }
    unsigned long long temp = a + b;
    a = b;
    b = temp;
  }
  std::cout << sum << std::endl;
  return 0;
}

View on GitHub

public class Euler002 {
    public static void main(String[] args) {
        long sum = 0;
        long a = 1, b = 2;
        while (b <= 4000000) {
            if (b % 2 == 0) {
                sum += b;
            }
            long temp = a + b;
            a = b;
            b = temp;
        }
        System.out.println(sum);
    }
}

View on GitHub

Solution Notes

Mathematical Background

The Fibonacci sequence is defined by the recurrence relation $F_n = F_{n-1} + F_{n-2}$ with initial conditions $F_1 = 1$ , $F_2 = 2$ . The sequence exhibits interesting properties regarding parity (even/odd distribution).

A key mathematical insight is that every third Fibonacci number is even. This occurs because:

$F_1 = 1$ (odd)
$F_2 = 2$ (even)
$F_3 = F_2 + F_1 = 2 + 1 = 3$ (odd)
$F_4 = F_3 + F_2 = 3 + 2 = 5$ (odd)
$F_5 = F_4 + F_3 = 5 + 3 = 8$ (even)
$F_6 = F_5 + F_4 = 8 + 5 = 13$ (odd)

This pattern continues: odd + odd = even, odd + even = odd, even + odd = odd, establishing the cycle every three terms.

Algorithm Analysis

The implementations use an iterative approach to generate Fibonacci numbers and sum the even terms. This has O(n) time complexity where n is the number of Fibonacci terms below 4,000,000.

A more mathematically sophisticated approach recognizes that even Fibonacci numbers follow the sequence $E_n = 2, 8, 34, 144, 610, 2584, \dots$ where each term is $4 \times E_{n-1} + E_{n-2}$ . This allows direct computation of even terms without checking parity.

The closed-form solution using the golden ratio $\phi = \frac{1+\sqrt{5}}{2}$ gives the nth Fibonacci number as $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ , though floating-point precision limits practical use for large n.

Key Insights

The iterative approach is simple and efficient for the given constraint (terms ≤ 4,000,000)
Every third Fibonacci number is even, enabling optimization for larger limits
The sequence grows exponentially, reaching 4 million around the 33rd term
Integer overflow becomes a concern in languages with fixed-size integers (like 32-bit int)
The pattern of even terms reveals deeper mathematical structure in the Fibonacci sequence

Educational Value

This problem introduces fundamental concepts in:

Sequence generation and recurrence relations
Pattern recognition in mathematical sequences
The importance of understanding number properties (parity)
Algorithm design choices between simplicity and mathematical optimization
Handling large numbers and overflow considerations in different programming languages
The connection between simple iterative solutions and underlying mathematical structure