Conway常数是怎么得来的？

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

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 常数。

我一直很好奇：这个 71 次方程是怎么来的啊？今天，我看到了 Conway 常数的一个推导www.nathanieljohnston.com/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/，终于解开了困扰我 N 久的谜题，在这里和大家分享一下。

Conway 常数的推导依赖于 Conway 发现的另一个定理：从第 8 个数开始，所有的数都是由 92 个“基本串”构成的。下面这个表格按照字典序列出了这 92 个基本串，以及每一个串的长度。列表的第 4 列给出了每个串迭代一次后会演变成哪些串。举例来说，第 2 个基本串是 1112133 ，它的下一个数就是 31121123 , 是由第 64 个基本串和第 62 个基本串拼接组成的。

外观数列的前 8 项分别是 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 。其中，第 8 项是由基本串 #24 和基本串 #39 组成的。在此之后，所有的数列都在基本串之间互相演变，构成了越来越长的数字串。可以说，这 92 个基本串就是 92 个原子，它们组成了外观数列世界中的各种数字串。在 MathWorld 的相关页面mathworld.wolfram.com/CosmologicalTheorem.html 上，甚至有这 92 个原子的“元素周期表”；表格里不但有元素的名称，还给出了每个元素的丰度。

有了上面这张表格，我们就能算出数列中的每一项的长度了。考虑一个 92 × 92 的矩阵 T ，其中第 i 列表示的就是基本串 ＃i 的演变情况。举例来说，基本串 #2 将会演化出 #64 和 #62，那么我们就令矩阵 T 的第 2 列第 64 行等于基本串 #64 与 #2 的长度比，而第 62 行则为基本串 #62 和 #2 的长度比。外观数列的第 8 项包含了基本串 #24 和 #39 ，它们俩的长度都是 5 。我们就用一个含 92 个元素的向量 A = (0, 0, …, 0, 5, 0, …, 0, 5, 0, 0, …, 0) 来表示外观数列第 8 项中各基本串所占的长度。于是， T * A 就反映了数列第 9 项的长度信息， T^2 * A 则对应数列的第 10 项⋯⋯于是我们便得到了一个数列长度的递推关系。

好在这个矩阵很稀疏，不难得到它的特征方程：

x^18 * (x + 1) * (x – 1)^2 * (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

舍去 0 、 1 、 -1 三个根，就只剩下这个 71 次方程了。这个 71 次方程恰有一个实根，它就是我们要找的数列增长速率。