Conway常数是怎么得来的？

2010 年 11 月 2 日 / 32 条评论

在所有寻找数字规律的谜题中，下面这个难题可能是最有意思的题目之一了：

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ⋯⋯
上面这个数列有什么规律？

若你是第一次听到这个问题，你一定会非常喜欢问题的答案：下一个数是对上一个数的描述，比方说 1211 里有 “ 1 个 1 ， 1 个 2 ， 2 个 1 ” ，那么 111221 就是它的下一个数。通常我们把这个数列叫做“外观数列”。
作为一个让人拍案叫绝的智力游戏，外观数列的故事似乎就已经到此为止了。可是，人们渐渐发现，外观数列里面还大有文章可做。例如，数列中的数虽然会越来越长，但数字 4 始终不会出现。这些优雅的性质成功地引来了数学家们的围观。在对外观数列的研究中，最引人注目的成果之一要归功于英国数学家 John Conway 。 1987 年， John Conway 发现，在这个数列中，相邻两数的长度之比越来越接近一个固定的数。最终，数列的长度增长率将稳定在 30% 左右。事实上，如果把数列中第 n 个数的长度记作 L_n ，则当 n 趋于无穷大的时候， L_(n+1) / L_n 将趋于一个极限。 John Conway 把这个极限用希腊字母 λ 表示，并证明了这个数是 71 次方程

x^71 – x^69 – 2*x^68 – x^67 + 2*x^66 + 2*x^65 + x^64 – x^63 – x^62 – x^61 – x^60 – x^59 + 2*x^58 + 5*x^57 + 3*x^56 – 2*x^55 – 10*x^54 – 3*x^53 – 2*x^52 + 6*x^51 + 6*x^50 + x^49 + 9*x^48 – 3*x^47 – 7*x^46 – 8*x^45 – 8*x^44 + 10*x^43 + 6*x^42 + 8*x^41 – 5*x^40 – 12*x^39 + 7*x^38 – 7*x^37 + 7*x^36 + x^35 – 3*x^34 + 10*x^33 + x^32 – 6*x^31 – 2*x^30 – 10*x^29 – 3*x^28 + 2*x^27 + 9*x^26 – 3*x^25 + 14*x^24 – 8*x^23 – 7*x^21 + 9*x^20 + 3*x^19 – 4*x^18 – 10*x^17 – 7*x^16 + 12*x^15 + 7*x^14 + 2*x^13 – 12*x^12 – 4*x^11 – 2*x^10 + 5*x^9 + x^7 – 7*x^6 + 7*x^5 – 4*x^4 + 12*x^3 – 6*x^2 + 3*x – 6 = 0

的唯一实数解，它约为 1.303577 。这就是传说中的 Conway 常数。

奇妙的心电图数列

2010 年 2 月 20 日 / 24 条评论

心电图数列 (EKG Sequence) 的定义简单而有趣：第一项为 1 ，第二项为 2 ，以后的每一项都是最小的和前一项不互质并且不曾出现过的数。换句话说，数列 a(1)=1 ， a(2)=2 ，且当 n>2 时取 a(n) 为所有满足以下两个条件的数中最小的那一个：该数与 a(n-1) 有大于 1 的公约数，并且该数与前面 n-1 项都不相等。心电图数列的前面 20 项为

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 …

为什么它叫做心电图数列呢？原因很简单——因为把它描绘在图象上时，看上去像一张心电图。

从“迷失的8”到生成函数：小数展开的秘密

2009 年 3 月 17 日 / 37 条评论

    小学时经常在计算器上面按12345679这个神秘的8位数。这个数牛就牛在，它乘以9的结果正好等于111111111。你可以在计算器上输好12345679，然后问MM“你的幸运数字是多少”；如果她说“7”，你就在计算器上按“乘以63”，计算器上将会显示出清一色的7字，看上去无比壮观。
    假如123456789×9=1111111111的话，我倒不会觉得奇怪。网上流行过一个火星帖子，写了一大堆诸如111111111 * 111111111 = 12345678987654321的式子来展示数学之美，以至于大家会认为123456789×9的结果也一定是一串很有规律的数字。因此，如果我不在这里说一句123456789×9其实并不等于1111111111的话，估计很多人都发现不了问题。事实上，123456789×9=1111111101，偏偏就差一个“1”。而怪就怪在，去掉被除数中的数字“8”，偏偏又有了12345679×9=111111111，一个极其别扭的算式反而得到了完美的结果。不要让你的直觉被数学之美所蒙蔽，数学上有大量出人意料的、看上去很不对称的结论。
    为什么偏偏要少一个“8”呢？难道这真的是算术中的一个不可抹去的疤痕？我们急需要寻求一个解释，填补上算术中的这个不和谐的“漏洞”。一种解释是，我们看到了123456789×9=1111111101并不美观，想要对其进行改造，进而得到(123456789+1)*9 = 1111111101+9 = 1111111110，于是(123456789+1)*9/10 = 12345679*9 = 111111111。用这种办法的确可以解释“迷失的8”，不过这个解释并不漂亮。为了寻求一个更好的解释，我们来看一看111111111和9的关系。

趣题：理想模型下的排序算法（下）

2009 年 3 月 6 日 / 23 条评论

上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。

这些序列都是自相似序列……

2009 年 2 月 2 日 / 14 条评论

如果说数学家是魔术师的话，无穷就是一根最强大的魔杖。在Manfred Schröder的一篇题为Fractals in Music的论文里，作者提到，把每个正整数对应的二进制数中“1”的个数依次写下来，得到的数列有一个很神奇的性质：划掉所有的奇数项，得到的序列仍然是整个序列本身。

十进制数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 二进制数 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1的个数 1 1 2 1 2 2 3 1 2 2 3 2 3 3 取偶数项 1 1 2 1 2 2 3

最初我是在《算法艺术与信息学竞赛》里见到这个东西的，当时硬是被震撼住了。这样的序列叫做“自相似序列”，意思是说自己的一部分等于本身。注意到，这个“自相似”可以无限制地进行下去。再次取出所得的序列中的偶数项，结果还是与最初的序列一样；再这样做下去做无数次，每一次的结果都会与原始序列相同。也就是说，无穷里面包含了无穷多个规模不同的无穷，并且所有这些无穷都和原来完全相同。不过呢，仔细一想你会发现这个一点也不奇怪，奥妙就在于，n和2n的二进制表达中唯一的差别就是末尾的那个“0”。