Contents 6 sections
  1. 先猜下一项
  2. 只有 1、2、3
  3. 长度增长约 30%
  4. 一张「元素周期表」
  5. 自己试试
  6. 记录这条数列的理由

先猜下一项

1,11,21,1211,111221,312211, ?1,\quad 11,\quad 21,\quad 1211,\quad 111221,\quad 312211,\quad \ ?

这是一道流传很广的智力题。它用不到任何算术,规则是:把上一项读出来。

  • 11 读作「一个 1」,记为 1111;
  • 1111 读作「两个 1」,记为 2121;
  • 2121 读作「一个 2、一个 1」,记为 12111211;
  • 12111211 读作「一个 1、一个 2、两个 1」,记为 111221111221;
  • 111221111221 读作「三个 1、两个 2、一个 1」,记为 312211312211。

所以下一项是 1311222113112221。这条数列叫作外观数列(look-and-say sequence),是 OEIS 中的 A005150。

把它当成猜谜题,到这里就结束了。可 John H. Conway 在 1980 年代认真研究了它,发现这条看似随意的数列里藏着一套完整的结构。

只有 1、2、3

多写几项就会注意到:数列里从来不出现 44。

命题 1

从 11 开始的外观数列中,每一项都只包含数字 11、22、33。

证明.

先证一个更强的事实:从第二项起,任何一项都不含连续四个相同的数字。

第 n+1n+1 项由若干「计数–数字」对拼成,每一对描述第 nn 项中的一段极长连续相同数字。两段相邻的极长段,数字一定不同。

假设第 n+1n+1 项中出现了连续四个 aa,按照它们在对中的位置分两种情况:

  • 四个 aa 恰好组成两个完整的对 (a,a)(a,a)(a, a)(a, a):说明第 nn 项中有一段 aa 个 aa,紧接着又是一段 aa 个 aa。这两段相邻且数字相同,与「极长」矛盾。
  • 四个 aa 跨过三个对,形如 (⋅,a)(a,a)(a,⋅)(\cdot, a)(a, a)(a, \cdot):中间两个对说明第 nn 项中先有一段数字 aa,紧接着又是一段数字 aa,同样矛盾。

所以从第二项起,连续相同数字最多三个。于是之后每一项里的「计数」只可能是 1,2,31, 2, 3;而被计数的「数字」都是从上一项抄下来的。从 11 出发归纳,所有数字都在 {1,2,3}\{1,2,3\} 中。

∎

这个证明对任何种子都适用:无论从什么数开始,第三项起「计数」位置只会出现 1、2、3,种子里原有的数字只是被原样抄下去。

长度增长约 30%

记第 nn 项的长度为 LnL_n,即 OEIS 中的 A005341:

相邻两项之比 Ln+1/LnL_{n+1}/L_n 起初跳来跳去,但很快就稳定下来:第 40 项有 63138 位,它与第 39 项长度之比约为 1.30421.3042。

定理 2(Conway)

lim⁡n→∞Ln+1Ln=λ=1.303577269034…\displaystyle\lim_{n\to\infty}\frac{L_{n+1}}{L_n} = \lambda = 1.303577269034\ldots,其中 λ\lambda 是一个 71 次整系数多项式唯一的正实根。

这个常数现在叫作Conway 常数(OEIS A014715)。

一张「元素周期表」

Conway 的证明思路非常有意思,他借用了化学的比喻。

他注意到,外观数列的项在演化中会「分裂」:某些位置两侧以后永远不会再互相影响。比如一项写成 ABAB,如果 AA 的末位和 BB 的首位以后永远不会读到同一段里去,那么 ABAB 的下一项就等于 AA 的下一项接上 BB 的下一项,两部分各自独立演化。

不能再分裂的最小片段,Conway 把它们叫作元素。他找到了恰好 92 个只由 1、2、3 组成的元素,并用氢到铀这 92 种化学元素给它们命名;每个元素在一步之后都会「衰变」成若干个元素的组合。例如最简单的元素「氢」就是 2222:读出来是「两个 2」,还是 2222。它是唯一一个永远不变的元素。

于是整条数列的演化,就化成了一个 92×9292 \times 92 的衰变矩阵:第 (i,j)(i,j) 个元素表示元素 jj 一步之后会产生几个元素 ii。长度的增长率就是这个矩阵最大的特征值,而它的特征多项式里有一个 71 次的不可约因子,λ\lambda 正是这个因子的根。

Conway 还证明了一个更强的结论,他称之为宇宙学定理:无论从什么种子出发(除了 2222 本身这个不动点),经过足够多步之后,每一项都会分裂成这 92 种元素以及另外两种「超铀元素」的组合。两种超铀元素对应种子中含有 4 及以上数字的情形。所以 Conway 常数是所有种子共同的增长率,与从哪里开始无关。

自己试试

换一个种子,看看长度之比是否还会趋于 1.30361.3036。

实验:从任意种子开始读数Lab · Look and say
试试 1、3、22、1113122113
n长度增长比这一项

记录这条数列的理由

外观数列不是从任何数学问题里自然产生的,规则甚至依赖于用十进制「读」数字。但只要认真对待它,就会出现分裂、元素、衰变矩阵,最后得到一个 71 次的代数数。一个看起来只是文字游戏的规则,背后有一套完整而精确的结构。