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

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

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

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

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

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

在翻 Matrix67 的思考的乐趣的时候, 看到集合论那里, 依次证明了有理数, 代数数, 可计算数, 可定义数的可数性, 甚舒畅. 然后用经典的 Cantor's Diagonal Argument 证了实数的不可数性, 并说明了此方法对有理数不可用, 因为对角线生成的新数未必是有理数.

然后我想, 对角线法用在可计算数上似乎也可以啊.. 假设可计算数可数, 排成一列 之后, 按照对角线法取出一数, 保证取出数 满足 , 则 也没有被列出. 而进一步, 如果我们规定取数时的对应法则 , 令 无不动点, , 那么取出的新数也就是可计算的了. 那按照 Diagonal Argument, 可计算数不就不可数了?