PE0002: Even Fibonacci Numbers | Zhen Lu

题目

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)

优点：逻辑简单，适合理解基础循环和条件判断。缺点：需检查每个数是否为偶数，效率较低（时间复杂度 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)

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

答案

答案为4613732。

--- title: "PE0002: Even Fibonacci Numbers" date: 2025-04-01 description: "Project Euler Problem 2: Even Fibonacci Numbers" image: "https://cdn.jsdelivr.net/gh/Leslie-Lu/WeChatOfficialAccount/img_2025/20250401160955.png" categories: - python - project euler - algorithm - math - programming - fibonacci format: html: shift-heading-level-by: 1 include-in-header: - text: | <style type="text/css"> hr.dinkus { width: 50px; margin: 2em auto 2em; border-top: 5px dotted #454545; } div.column-margin+hr.dinkus { margin: 1em auto 2em; } </style> --- ## 题目 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: <div style="text-align:center;"> 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... </div> 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等）的总和。 ## 解答 ### 方法一：直接遍历法（新手友好）思路：逐个生成斐波那契数，检查是否为偶数，累加符合条件的项。 ```{python} 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) ``` 优点：逻辑简单，适合理解基础循环和条件判断。缺点：需检查每个数是否为偶数，效率较低（时间复杂度 `O(n)`）。 ### 方法二：生成器 + NumPy（效率升级）思路：用生成器无限生成斐波那契数，结合NumPy数组快速筛选偶数。 ```{python} # 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 ``` 优点：生成器减少内存占用，NumPy向量化操作加速计算。缺点：仍需生成全部数列，大范围数据仍不够高效。 ### 方法三：数学优化法核心发现：斐波那契数列中，每第三项为偶数（如2, 8, 34, 144...）。利用此规律，只需计算这些特定项的和，跳过无关项，效率飙升。 ```{python} 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) ``` 优点：时间复杂度降至 `O(log n)`，四千万甚至十亿级数据也能瞬间完成。 ## 答案答案为4613732。