002 - Even Fibonacci Numbers

Overview

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

def solution(n: int):
    total = 0
    a, b = 2, 8
    total += a
    while b <= n:
        total += b
        a, b = b, 4 * b + a
    return total

Benchmarks

======================================================================
🕵️  AUDITING PROJECT EULER ARCHITECTURE: solution()
======================================================================
Result Yielded         : 4613732
Average Execution Time : 1.93 microseconds
Peak Memory Allocated  : 0.06 KB
Algorithmic Scaling    : 1.20x time growth on 10x input
======================================================================

The Mathematical Rationale

1. Parity Pattern Matrix

Let us analyze the parity (odd/even status) of the standard Fibonacci sequence starting from 1 and 2:

F(1) = 1 (Odd)
F(2) = 2 (Even)
F(3) = 1 + 2 = 3 (Odd)
F(4) = 2 + 3 = 5 (Odd)
F(5) = 3 + 5 = 8 (Even)
F(6) = 5 + 8 = 13 (Odd)
F(7) = 8 + 13 = 21 (Odd)
F(8) = 13 + 21 = 34 (Even)

Notice the recurring pattern: Odd, Even, Odd, Odd, Even, Odd, Odd, Even… Because the sum of two odd numbers is even, and the sum of an odd and an even number is odd, every third Fibonacci number is guaranteed to be even.

2. Deriving the Direct Recurrence Relation

Instead of checking every number, we can derive a direct formula to compute the next even Fibonacci number (E_n) using only the previous even numbers (E_n-1 and E_n-2).

By working backwards through the standard Fibonacci definition (F_n = F_n-1 + F_n-2), we can unfold the algebra:

Let E_n be the current even term.
The previous even term (E_n-1) is 3 steps back.
The even term before that (E_n-2) is 6 steps back.

Expanding the algebraic substitutions reveals a beautiful simplified identity:

E_n = 4 × E_n-1 + E_n-2

Step-by-Step Proof Summary:

Start with an even term: F_n
F_n = F_n-1 + F_n-2
Substitute F_n-1 = F_n-2 + F_n-3 → F_n = 2 × F_n-2 + F_n-3
Substitute F_n-3 = F_n-4 + F_n-5 → F_n = 2 × F_n-2 + F_n-4 + F_n-5
Ultimately, re-grouping to look only at the third-step indices simplifies down to the clean relation: Next = 4 × Current + Previous.

Given our starting even numbers are 2 and 8, the sequence progresses instantly as:

2
8
4 × 8 + 2 = 34
4 × 34 + 8 = 144
4 × 144 + 34 = 610

Complexity Analysis

Metric	Traditional Scan	Optimized Skipping Framework
Time Complexity	O(N)	O(N) (But executes 3x fewer iterations)
Space Complexity	O(1)	O(1)
Evaluation Footprint	Evaluates every term ( $F_{n}$ ). Checks conditions.	Evaluates only even terms. Zero conditional statements inside the loop.

ആരാമം

Explorer