Problem 2: Even Fibonacci Numbers

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.

Approach

Iterative Generation

Generate Fibonacci numbers iteratively and sum only the even values:

int sum = 0;
int a = 1, b = 2;

while (b <= 4000000) {
    if (b % 2 == 0) {
        sum += b;
    }
    int next = a + b;
    a = b;
    b = next;
}

Optimized Approach

Observe that in the Fibonacci sequence, every third number is even. We can skip the odd numbers entirely:

Starting with 2, 8, 34, 144, … (even Fibonacci numbers) The pattern follows: F(n) = 4×F(n-1) + F(n-2)

Key Insights

• Fibonacci sequence has a pattern where every 3rd number is even
• No need to check divisibility by 2 for every number
• Can directly generate only even Fibonacci numbers

Complexity

• Time Complexity: O(log n) where n is the upper limit (4 million)
• Space Complexity: O(1)

Solution

View the complete solution on GitHub.

Related Concepts

• Fibonacci sequence
• Number patterns and sequences
• Iterative algorithms