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 常数的一个推导,终于解开了困扰我 N 久的谜题,在这里和大家分享一下。

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

# Subsequence Length Evolves Into
1 1112 4 (63)
2 1112133 7 (64)(62)
3 111213322112 12 (65)
4 111213322113 12 (66)
5 1113 4 (68)
6 11131 5 (69)
7 111311222112 12 (84)(55)
8 111312 6 (70)
9 11131221 8 (71)
10 1113122112 10 (76)
11 1113122113 10 (77)
12 11131221131112 14 (82)
13 111312211312 12 (78)
14 11131221131211 14 (79)
15 111312211312113211 18 (80)
16 111312211312113221133211322112211213322112 42 (81)(29)(91)
17 111312211312113221133211322112211213322113 42 (81)(29)(90)
18 11131221131211322113322112 26 (81)(30)
19 11131221133112 14 (75)(29)(92)
20 1113122113322113111221131221 28 (75)(32)
21 11131221222112 14 (72)
22 111312212221121123222112 24 (73)
23 111312212221121123222113 24 (74)
24 11132 5 (83)
25 1113222 7 (86)
26 1113222112 10 (87)
27 1113222113 10 (88)
28 11133112 8 (89)(92)
29 12 2 (1)
30 123222112 9 (3)
31 123222113 9 (4)
32 12322211331222113112211 23 (2)(61)(29)(85)
33 13 2 (5)
34 131112 6 (28)
35 13112221133211322112211213322112 32 (24)(33)(61)(29)(91)
36 13112221133211322112211213322113 32 (24)(33)(61)(29)(90)
37 13122112 8 (7)
38 132 3 (8)
39 13211 5 (9)
40 132112 6 (10)
41 1321122112 10 (21)
42 132112211213322112 18 (22)
43 132112211213322113 18 (23)
44 132113 6 (11)
45 1321131112 10 (19)
46 13211312 8 (12)
47 1321132 7 (13)
48 13211321 8 (14)
49 132113212221 12 (15)
50 13211321222113222112 20 (18)
51 1321132122211322212221121123222112 34 (16)
52 1321132122211322212221121123222113 34 (17)
53 13211322211312113211 20 (20)
54 1321133112 10 (6)(61)(29)(92)
55 1322112 7 (26)
56 1322113 7 (27)
57 13221133112 11 (25)(29)(92)
58 1322113312211 13 (25)(29)(67)
59 132211331222113112211 21 (25)(29)(85)
60 13221133122211332 17 (25)(29)(68)(61)(29)(89)
61 22 2 (61)
62 3 1 (33)
63 3112 4 (40)
64 3112112 7 (41)
65 31121123222112 14 (42)
66 31121123222113 14 (43)
67 3112221 7 (38)(39)
68 3113 4 (44)
69 311311 6 (48)
70 31131112 8 (54)
71 3113112211 10 (49)
72 3113112211322112 16 (50)
73 3113112211322112211213322112 28 (51)
74 3113112211322112211213322113 28 (52)
75 311311222 9 (47)(38)
76 311311222112 12 (47)(55)
77 311311222113 12 (47)(56)
78 3113112221131112 16 (47)(57)
79 311311222113111221 18 (47)(58)
80 311311222113111221131221 24 (47)(59)
81 31131122211311122113222 23 (47)(60)
82 3113112221133112 16 (47)(33)(61)(29)(92)
83 311312 6 (45)
84 31132 5 (46)
85 311322113212221 15 (53)
86 311332 6 (38)(29)(89)
87 3113322112 10 (38)(30)
88 3113322113 10 (38)(31)
89 312 3 (34)
90 312211322212221121123222113 27 (36)
91 312211322212221121123222122 27 (35)
92 32112 5 (37)

    外观数列的前 8 项分别是 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 。其中,第 8 项是由基本串 #24 和基本串 #39 组成的。在此之后,所有的数列都在基本串之间互相演变,构成了越来越长的数字串。可以说,这 92 个基本串就是 92 个原子,它们组成了外观数列世界中的各种数字串。在 MathWorld 的相关页面 上,甚至有这 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 次方程恰有一个实根,它就是我们要找的数列增长速率。

32 条评论

回复给 biohu 取消回复

9  ×    =  81