How Many Fibonacci Numbers are also Power of 2

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

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

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

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

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

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

Cantor's Diagonal Method on Computable Numbers

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

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

Read more