先猜下一项
这是一道流传很广的智力题。它用不到任何算术,规则是:把上一项读出来。
- 读作「一个 1」,记为 ;
- 读作「两个 1」,记为 ;
- 读作「一个 2、一个 1」,记为 ;
- 读作「一个 1、一个 2、两个 1」,记为 ;
- 读作「三个 1、两个 2、一个 1」,记为 。
所以下一项是 。这条数列叫作外观数列(look-and-say sequence),是 OEIS 中的 A005150。
把它当成猜谜题,到这里就结束了。可 John H. Conway 在 1980 年代认真研究了它,发现这条看似随意的数列里藏着一套完整的结构。
只有 1、2、3
多写几项就会注意到:数列里从来不出现 。
从 开始的外观数列中,每一项都只包含数字 、、。
先证一个更强的事实:从第二项起,任何一项都不含连续四个相同的数字。
第 项由若干「计数–数字」对拼成,每一对描述第 项中的一段极长连续相同数字。两段相邻的极长段,数字一定不同。
假设第 项中出现了连续四个 ,按照它们在对中的位置分两种情况:
- 四个 恰好组成两个完整的对 :说明第 项中有一段 个 ,紧接着又是一段 个 。这两段相邻且数字相同,与「极长」矛盾。
- 四个 跨过三个对,形如 :中间两个对说明第 项中先有一段数字 ,紧接着又是一段数字 ,同样矛盾。
所以从第二项起,连续相同数字最多三个。于是之后每一项里的「计数」只可能是 ;而被计数的「数字」都是从上一项抄下来的。从 出发归纳,所有数字都在 中。
∎这个证明对任何种子都适用:无论从什么数开始,第三项起「计数」位置只会出现 1、2、3,种子里原有的数字只是被原样抄下去。
长度增长约 30%
记第 项的长度为 ,即 OEIS 中的 A005341:
相邻两项之比 起初跳来跳去,但很快就稳定下来:第 40 项有 63138 位,它与第 39 项长度之比约为 。
,其中 是一个 71 次整系数多项式唯一的正实根。
这个常数现在叫作Conway 常数(OEIS A014715)。
一张「元素周期表」
Conway 的证明思路非常有意思,他借用了化学的比喻。
他注意到,外观数列的项在演化中会「分裂」:某些位置两侧以后永远不会再互相影响。比如一项写成 ,如果 的末位和 的首位以后永远不会读到同一段里去,那么 的下一项就等于 的下一项接上 的下一项,两部分各自独立演化。
不能再分裂的最小片段,Conway 把它们叫作元素。他找到了恰好 92 个只由 1、2、3 组成的元素,并用氢到铀这 92 种化学元素给它们命名;每个元素在一步之后都会「衰变」成若干个元素的组合。例如最简单的元素「氢」就是 :读出来是「两个 2」,还是 。它是唯一一个永远不变的元素。
于是整条数列的演化,就化成了一个 的衰变矩阵:第 个元素表示元素 一步之后会产生几个元素 。长度的增长率就是这个矩阵最大的特征值,而它的特征多项式里有一个 71 次的不可约因子, 正是这个因子的根。
Conway 还证明了一个更强的结论,他称之为宇宙学定理:无论从什么种子出发(除了 本身这个不动点),经过足够多步之后,每一项都会分裂成这 92 种元素以及另外两种「超铀元素」的组合。两种超铀元素对应种子中含有 4 及以上数字的情形。所以 Conway 常数是所有种子共同的增长率,与从哪里开始无关。
自己试试
换一个种子,看看长度之比是否还会趋于 。
| n | 长度 | 增长比 | 这一项 |
|---|
记录这条数列的理由
外观数列不是从任何数学问题里自然产生的,规则甚至依赖于用十进制「读」数字。但只要认真对待它,就会出现分裂、元素、衰变矩阵,最后得到一个 71 次的代数数。一个看起来只是文字游戏的规则,背后有一套完整而精确的结构。