How Many Fibonacci Numbers are also Power of 2

数据结构课上, 比较二分查找与 Fibonacci 查找. 举例时为了方便, 就让数组长度是 8, 因为 8 既是 2 的幂又是 Fibonacci 数, 方便演示算法. 邓俊辉老师随口问了一句像这样的数还有没有呢. 答案是没有的.

Fibonacci 数有一个有趣等价条件: 是 Fibonacci 数当且仅当 中某一个数是完全平方数.

• 必要性很好证. 验证如下等式: 其中 是以 定义的 Fibonacci 数, 是以 定义的 Lucas 数

• 充分性: 于是 为 中的单位元, 那么 , 就可以得到 了.

有了这个性质之后, 只需要考虑 有没有非平凡解即可. 这个很容易就.. 略了.

后来发现一个很强的 Carmichael 定理, 可以直接秒这道题. 定理的内容是: 对每个 必定包含一个没有在之前的 Fibonacci 序列中出现的因子.