斐波那契偶数

受到Fibonacci帖子接受评论的启发。 用户pavellyzhin提到了以下采访任务（ 评论 ）：

一年多以前，“ php程序员”对空缺做出了回应，他们发送了TK，而斐波那契有一个任务： 选择甚至1到10000之间的所有斐波那契数 。 决定使用（for）循环。 在那儿，还必须进行SQL查询以选择最近的用户生日，以弥补某些东西，我只是不记得并编写了某种函数。 我做了一切，发送了。 他们发送了一个答案：“根据测试任务的结果，您不被接受。” 他们到底不喜欢什么，没有写出来。 现在我坐在那里思考，可能毕竟是因为斐波那契我飞了……:)

在这篇文章中，我将展示如何有效地，甚至可能有效地解决这个问题，但这并不准确。 同时，我将证明有关斐波那契数的成千上万的事实。

理论化

最好的开始方法是通过第一个N斐波那契数字的眼睛看，并尝试找到偶数排列的模式。

$$

$$1.1，{\ bf 2}，3.5，{\ bf 8}，13.21，{\ bf 34}，55.89，{\ bf 144}，\ ldots$$

偶数在序列中标记，因为您可以看到每个第三个斐波那契数都是偶数，而且很可能所有偶数都位于3的倍数的位置。这是我们的猜测，现在我们需要确认它并制定一个计算算法。

最好的证明很简单，因此感谢AllexIn我最初想念的简单想法。 每个随后的斐波那契数是前两个数的和，如果前两个数是奇数，则下一个将是偶数，如果在前两个数中一个是奇数，另一个是偶数，则下一个是奇数。 原则上，仅此想法就足以“直观地摸索”已证实的事实。 归纳证明是显而易见的，但我无法抗拒，以免带来

我们证明“每第三个斐波那契数都是偶数，而每个这样的数前两个是奇数”。

• 基地归纳 。 前两个斐波那契数 $$$1.1$ -奇数，第三个数字 $$$2$ -甚至
• 假说 。 假设不超过3的斐波那契数的倍数，则每三分之一都是偶数，而前面的两个都是奇数。
• 归纳步骤 。 假设中最后一个偶数后面的数字是奇数，因为 它是从奇数和偶数之和得出的，跟随该数字也已经是奇数，因为 它是从具有奇数的偶数之和与它的偶数后的下一个之和获得的，因为 刚收到给他的前两个是奇数，按构造，他的数是3的倍数，是偶数，前两个是奇数。

这样我们就可以证明我们的猜测，而无需借助数学计算。 您可以将此想法形式化，同时获得用于计算每三个斐波那契数的公式 $$$F_ {n + 3}$ 来自 $$$F_n$ 和 $$$F_ {n + 1}$ 。 使用递归关系 $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ 我们得到：

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

所以如果 $$$F_n$ -即使如此 $$$F_ {n + 3}$ 甚至借助这个公式。 鉴于 $$$F_3 = 2$ ，那么每三个斐波那契数实际上都是偶数，这证实了我们的部分猜测。 在这里您需要确保我们不会错过其他偶数，即 它们都是3的倍数。感谢janatem的简单想法，因为从上面的公式 $$$F_ {n + 3}$ 也可以得出结论，如果 $$$F_n$ -那么奇怪 $$$F_ {n + 3}$ 也很奇怪，所以我们用数字得到那个数字 $$$3k-2,3k-1，k \ in \ mathbb {N}$ -奇数（通过归纳，从 $$$F_1 = F_2 = 1$ -奇怪），和 $$$3k，k \ in \ mathbb {N}$ -偶数涵盖了所有斐波那契数，这意味着我们实际上涵盖了所有偶数。

还有另一种方法，因为有可能表明没有其他偶数。 假设存在一个数字 $$$F_m$ -甚至 $$$0 \不是\等值m \ mod 3$ 然后 $$$m = 3k-1$ 或 $$$m = 3k +1$ 在哪里 $$$k$ -一种自然的。

让我们转到原始帖子中的斐波那契数的矩阵表示

$$

$$\开始{pmatrix} 0＆1 \\ 1＆1 \结束{pmatrix} ^ n = \开始{pmatrix} F_ {n-1}＆F_n \\ F_n＆F_ {n + 1} \ end {pmatrix}$$

计算这两部分的行列式，我们得到

$$

$$（-1）^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

因此，数字的除数 $$$F_ {n + 1}，F_n$ 和 $$$F_ {n-1}，F_n$ 比赛分隔线 $$$（-1）^ n$ ，即 相邻的斐波那契数是相互简单的。 这也意味着相互简单和数量 $$$F_ {3k}，F_ {3k-1}$ 和 $$$F_ {3k}，F_ {3k + 1}$ ，即 $$$F_ {3k}$ 和 $$$F_m$ 。 但是假设 $$$F_m$ -甚至 $$$F_ {3k}$ -甚至以前已经证明过。 所以除了 $$$F_ {3k}$ 在哪里 $$$k \ in \ mathbb {N}$ 在斐波那契数列中不存在。 我们还建立了一个有趣的事实，即相邻的斐波那契数是相互简单的。

最后，我们展示至少另一种方法来证明我们的猜测：使用卢克定理。

卢克定理 。 整数除法 $$$F_m$ 和 $$$F_n$ ，当且仅当它是除数 $$$F_d$ 在哪里 $$$d = \ gcd（m，n）$ 特别是

$$

$$\ gcd（F_m，F_n）= F _ {\ gcd（m，n）}$$

在这里 $$$\ gcd$ 是最大的共同因素。 如果放 $$$m = 3$ 然后 $$$\ gcd（2，F_n）= F _ {\ gcd（3，n）}$ 。 如果 $$$F_n$ -即使左侧等于2，因此右侧也等于2，因此必须 $$$n$ 除以3并同时得出相反的结论。 因此，我们得到了我们想要证明的。

因此，斐波那契数字中的第三个数字是偶数，而每个偶数都是三的倍数。 我们已经仔细证明了这一点，现在没有人敢怀疑。

演算法

现在，仍然需要提出一种算法。 您当然可以做pavellyzhin最初做的事情，但无需检查 $$$0 \当量F_n \ mod 2$ 我们可以检查 $$$0 \等值n \ mod 3$ ，这是一个转折！ 没错，这不会影响算法的迭代次数，因为我们只是更改了序列过滤器。 最好立即生成具有所需属性（奇偶校验）的斐波那契数的子序列，因此另一种明显的方法是使用Binet公式

$$

$$F_n = \左\ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \右\ rceil，\ qquad n \ in \ {3,6，\ ldots，3k \ ldots \}$$

计算效率存在困难，有关更多信息，请参见原始帖子。 因此，我认为最好的方法是迭代计算 $$$F_ {n + 3}$ ，正如我们之前所展示的，可以通过公式完成 $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ 。 为了在算法中构造一个迭代过渡，我们需要计算 $$$F_ {n + 4}$ ，一切都一样简单

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

顺便说一句，通常来说，很容易证明

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

然后正式将算法编写如下（当前偶数斐波那契数 $$$F_n$ 其次是斐波那契数 $$$F_ {n + 1}$ ， $$$M$ 是问题条件中给出的数字的上限）：

1. $$$F_n \ leftarrow F_3 = 2，\ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. 如果 $$$F_n> M$ ，然后完成，否则添加到结果中 $$$F_n$
3. $$$（F_n，F_ {n + 1}）\ leftarrow（2F_ {n + 1} + F_n，3F_ {n + 1} + 2F_n）$ 转到步骤2。

该算法非常简单-我们只需跳到第三个斐波那契数并打印（如果不是更多的话） $$$M$ ） 该算法的复杂度仍然是线性的，但是步骤2的重复次数恰好等于该范围内的偶数斐波纳契数 $$$1 \ ldots M$ 相比之下，具有过滤功能的简单算法需要3倍以上的迭代次数（每发现一次，将丢弃2次）。

该算法存在于纸上，什么是PHP？ 好吧，最后揭开PHP的含义

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

注意 ：总是可以改进此方法，例如hunroll用户所示 。 这个想法是，对于计算，我们不需要多余的东西，除了部分获得的结果，即 我们可以只使用以前的偶数斐波那契数来计算偶数。

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n +（ F_ {n-1} + F_ {n-2}）+ F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

泛化

我们在这里提到了卢克定理， $$$\ gcd（F_m，F_n）= F _ {\ gcd（m，n）}$ 。 结果，我们可以得到斐波那契数 $$$F_n$ 的倍数 $$$F_m$ ，当且仅当其编号为 $$$n$ 多对数 $$$m$ 。 即 每4个斐波纳契数除以3，每5个数除以5，每6个数除以8，依此类推。

然后，以一种简单的方式，获得一种用于计算斐波那契子序列的算法，其中元素是某个给定数的倍数 $$$F_m$ 。 利用事实

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m +1} F_ {n + 1} + F_mF_n$$

以前的算法变成

1. $$$F_n \ leftarrow F_m，\ quad F_ {n + 1} \ leftarrow F_ {m + 1}$
2. 如果 $$$F_n> M$ ，然后完成，否则添加到结果中 $$$F_n$
3. $$$（F_n，F_ {n + 1}）\左箭头（F_mF_ {n + 1} + F_ {m-1} F_n，F_ {m +1} F_ {n + 1} + F_mF_n）$ 转到步骤2。

哪里 $$$F_ {m-1}，F_m，F_ {m + 1}$ 可以设置为常量。

注释摘要 。 正如用户的无知正确地指出的那样，在一般情况下，还可以构造仅使用部分结果中的数字的算法。

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n}-F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n}-F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} =（F_t + 2F_ {t-1}）F_n +（-1）^ {t-1} F_ {nt}$$

让我们通过数学归纳法证明这一点，对于t = 1和t = 2，满足是显而易见的。 假设它最多容纳t；然后

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\（F_t + 2F_ {t-1}）F_n +（-1）^ {t-1} F_ {nt} + \\（F_ {t-1} + 2F_ {t-2}）F_n +（-1）^ {t-2} F_ {n-t + 1} = \\（F_t + F_ { t-1} + 2（F_ {t-1} + F_ {t-2}））F_n +（-1）^ {t-1}（F_ {nt} -F_ {n-t + 1}）= \\（F_ {t + 1} + 2F_t）F_n +（-1）^ {t-1}（F_ {nt} -F_ {nt} -F_ {nt-1}）= \\（F_ {t + 1} + 2F_t）F_n +（-1）^ tF_ {nt-1}$$

总的来说

当然，任务是完全合成的，迭代次数非常小（对于 $$$M = $ 10,00$ 答案仅包含6个数字，即 6次迭代将已经完成，并且原始的“正面”算法将需要18），但是通过这种方式，在此处发现新内容的用户现在可以在面试时显示斐波纳契数的更深层的数学知识。

编辑：感谢janatem和AllexIn用户提供的简单证明，我将它们包括在“定理”中，并且仅使用在计算中已经获得的偶数来表示算法的粗略表述 ，并且对用户无知进行了概括。