题目原文

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,\dots$$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

形式化题意

定义数列

$$F_1=1,F_2=2,F_n=F_{n-1}+F_{n-2}(n\ge 3).$$

求

$$S=\sum _{\begin{array}{c}n\ge 1\\ F_n\le 4\times {10}^6\\ 2\mid F_n\end{array}}{F}_n.$$

提示

每次打开一个

写出连续斐波那契数的奇偶模式。

每三个斐波那契数中恰好有一个偶数。

解答

认真尝试后再打开

解题思路

斐波那契数列的奇偶性每三项循环一次：奇、偶、奇，因此每隔三项恰好出现一个偶数项。把所有偶数项依次记为 $E_1,E_2,\dots$，消去相邻偶数项之间的两个奇数项，可以得到

$$E_k=4E_{k-1}+E_{k-2}.$$

从第一个偶数项出发，这个递推只访问真正需要累加的项，不必生成并判断中间的奇数项，同时仍然可以用一个很短的循环完成计算。

代码与最终结果

密码保护内容

输入访问密码后，内容只会在当前浏览器中解密。

访问密码

题目原文引自 Project Euler 第 2 题，依据 CC BY-NC-SA 4.0 使用。