Sum of Even Fibonacci Numbers

Posted on Jul 04, 2023 By ᵇᵒ

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 开始生成的斐波那契数列的前 10 项为：
1,2,3,5,8,13,21,34,55,89,...

考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。

solution 1

对斐波那契数列中的每一项判断奇偶性，偶数相加求和：

pub fn sum_of_even_fibonacci_numbers(limit: i32) -> i32 {
    let mut sum = 0;
    let mut a = 1;
    let mut b = 1;
    while b < limit {
        if b & 0x01 == 0 { sum += b }
        let c = a + b;
        a = b;
        b = c;
    }
    sum
}

solution 2

不难证明，斐波那契数列每间隔三个为一个偶数。更通用的来说，斐波那契数列 F(n) 与 F(n-3) 具有相同的奇偶性(可以使用归纳法证明)：

pub fn sum_of_even_fibonacci_numbers(limit: i32) -> i32 {
    let mut sum = 0;
    let mut a = 1;
    let mut b = 1;
    let mut c = a + b;
    while c < limit {
        sum += c;
        a = b + c;
        b = c + a;
        c = a + b;
    }
    sum
}

solution 3

斐波那契数偶数数列：

2,8,34,144,...

仔细观察该数列不难发现也存在一种排列关系： E(n)=4*E(n-1)+E(n-2)

当然，证明也很简单。由斐波那契数数列公式 F(n)=F(n-1)+F(n-2) => F(n)=4*F(n-3)+F(n-6)，再叠加 solution 2 的思想每两个偶数间隔相差为3，即可变换得到 E(n)=4*E(n-1)+E(n-2)：

pub fn sum_of_even_fibonacci_numbers(limit: i32) -> i32 {
    let mut sum = 0;
    let mut a = 0;
    let mut b = 2;
    while b < limit {
        sum += b;
        let c = 4 * b + a;
        a = b;
        b = c;
    }
    sum
}

test

#[test]
fn test_sum_of_even_fibonacci_numbers() {
    assert_eq!(sum_of_even_fibonacci_numbers(4_000_000), 4_613_732);
}