PE0002: Even Fibonacci Numbers

Project Euler 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.

问题描述

题目要求：找出斐波那契数列中不超过四百万的所有偶数项，并计算它们的和。 斐波那契数列以1和2开始，后续项由前两项相加生成，例如：1, 2, 3, 5, 8, 13, 21, 34… 目标：求所有偶数项（如2、8、34等）的总和。

解答

方法一：直接遍历法（新手友好）

思路：逐个生成斐波那契数，检查是否为偶数，累加符合条件的项。

def sum_of_even_fibonacci(limit) -> int:
    """Returns the sum of even Fibonacci numbers not exceeding the limit."""
    a, b = 1, 2
    total = 0
    while a <= limit:
        if a % 2 ==0:
            total += a
        a, b= b, a+b
    return total

sum_of_even_fibonacci(4_000_000)

4613732

优点：逻辑简单，适合理解基础循环和条件判断。 缺点：需检查每个数是否为偶数，效率较低（时间复杂度 O(n)）。

方法二：生成器 + NumPy（效率升级）

思路：用生成器无限生成斐波那契数，结合NumPy数组快速筛选偶数。

# solution using a more efficient method
def fibonacci():
    """Generator for Fibonacci numbers"""
    a= b= 1
    while True:
        yield b
        a, b= b, a+b

series= []
for num in fibonacci():
    if num > 4_000_000:
        break
    series.append(num)

# series

import numpy as np
arr= np.array(series)
arr[arr%2==0].sum()  # sum of even Fibonacci numbers

np.int64(4613732)

优点：生成器减少内存占用，NumPy向量化操作加速计算。 缺点：仍需生成全部数列，大范围数据仍不够高效。

方法三：数学优化法

核心发现：斐波那契数列中，每第三项为偶数（如2, 8, 34, 144…）。 利用此规律，只需计算这些特定项的和，跳过无关项，效率飙升。

def SumThirdValue(limit) -> int:
    """
    Every third Fibonacci number is even.
    """
    x= y= 1
    sum= 0
    while x<= limit:
        sum+= (x+y)
        x, y= x+2*y, 2*x+3*y
    return sum

SumThirdValue(4_000_000)

4613732

优点：时间复杂度降至 O(log n)，四千万甚至十亿级数据也能瞬间完成。

答案

答案为4613732。