边看边说序列的宇宙学（五）

作者：安迁

六、具体的应用：“1”，“2”和“3”的比例

先解释一下这里“应用”的意思。许多读者看到这个理论的第一个（或第二个第三个……）反应也许会是“那这个理论在实际中有什么用途呢？

边说边看理论中的“说”“看”过程其实是一种被称为“游程编码”的编码方式。这种编码方式有时被用作数据压缩的方式，如在一些图像格式中。也许因为是这个原因，康威的论文在第二次发表时，刊登在一本和通信有关的学术论文集上。（第一次发表在剑桥大学数学学会的会刊Eureka上。）如果要强调边看边说理论有什么实际应用，也许这是个好的切入点。

不过我觉得这理论其实并没有什么实际用途，至少到目前为止没看见它有。它的价值在于它的美，而它的美源于它起源的质朴和内容的（相对）深刻以及形式的奇诡之间的强烈对比。一个数学理论，它是美的，这就是很好的价值了。

本节和后面所说的“应用”，是用康威的理论去回答一些问题。这些问题并不依赖于理论而存在；从原则上说，以直接产生边看边说序列再作观察的方式也能回答这些问题；但从现实上这样做非常困难，或根本不可能。本节想问的问题就是，从1开始的边看边说序列，它的第100，或是第1000000项有多少个数字，其中分别有多少“1”，“2”和“3”？

用直接写出每一项的方法，我们很容易计算出这个序列的前面几项的长度： 1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, …… 但是这个直接生成数字串并作统计的方法会变得越来越困难，所需要的计算量和储存空间越来越大。根据算术定理，序列长度以指数增长。取康威常数为1.3，以非常粗略的方式估计，它的第100项的长度大约会是1.3¹⁰⁰≈2×10¹¹，也就是千亿这个数量级，生成新数字串的计算量变得非常大。而它的第1000项的长度则要超过10¹⁰⁰，此时光是储存数字串也变得不可能，因为可观测宇宙内的原子总量据估计也仅有10⁸⁰个。如果我们想知道第1000000项数字串有多长，其中分别有多少“1”，“2”和“3”，靠直接生成数字串的方法是完全不可行的。

但通过康威理论，这个问题就容易解决了。

我们知道，从数字串1开始的边看边说序列在第8项演化成由一个₇₂铪元素和一个₅₀锡元素组成的化合物。从这一天起，通过查询元素列表中的“一天后衰变物”一栏，每天演化出来的化合物中的各元素数量都可以通过前一天化合物中各元素的数量来计算：比如说，如果前一天的化合物中有100个₃₁镓元素，那么次日的化合物中就会因此产生100个₁氢元素，200个₂₀钙元素，100个₃₀锌元素，100个₆₃铕元素和100个₈₉锕元素。由分割的原理，化合物中的每一个元素都可以看作是在独立演化而不和化合物中其他（同种或不同种的）元素的演化过程相互干扰。92种元素中的每一种都可如此算出次日产生的元素数量，求和后就可得出次日产生的化合物中每种元素的含量。下面给出了第8项到第20项以及第99和第100项的结果：

项	化合物中元素个数
8	₅₀锡:1, ₇₂铪:1
9	₄₉铟:1, ₇₁镥:1
10	₄₈镉:1, ₇₀镱:1
11	₄₇银:1, ₆₉铥:1
12	₂₀钙:1, ₂₇钴:1, ₄₆钯:1, ₆₈铒:1
13	₁₉钾:1, ₂₆铁:1, ₄₅铑:1, ₆₁钷:1, ₆₇钬:1
14	₁₈氩:1, ₂₅锰:1, ₄₄钌:1, ₆₀钕:1, ₆₆镝:1, ₆₇钬:1
15	₁₄硅:1, ₁₇氯:1, ₂₀钙:1, ₂₄铬:1, ₄₃锝:1, ₅₉镨:1, ₆₃铕:1, ₆₅铽:1, ₆₆镝:1
16	₁₃铝:1, ₁₆硫:1, ₁₉钾:1, ₂₃钒:1, ₄₂钼:1, ₅₈铈:1, ₆₂钐:1, ₆₄钆:1, ₆₅铽:1, ₆₇钬:1
17	₁氢:1, ₁₂镁:1, ₁₅磷:1, ₁₈氩:1, ₂₀钙:3, ₂₂钛:1, ₂₇钴:2, ₃₀锌:1, ₄₁铌:1, ₅₇镧:1, ₆₁钷:1, ₆₃铕:1, ₆₄钆:1, ₆₆镝:1, ₆₇钬:1
18	₁氢:1, ₁₁钠:1, ₁₄硅:1, ₁₇氯:1, ₁₉钾:3, ₂₀钙:1, ₂₁钪:1, ₂₆铁:2, ₂₇钴:1, ₂₉铜:1, ₄₀锆:1, ₅₆钡:1, ₆₀钕:1, ₆₁钷:1, ₆₂钐:1, ₆₃铕:1, ₆₅铽:1, ₆₆镝:1, ₆₇钬:1, ₆₈铒:1
19	₁氢:3, ₁₀氖:1, ₁₃铝:1, ₁₆硫:1, ₁₈氩:3, ₁₉钾:1, ₂₀钙:3, ₂₅锰:2, ₂₆铁:1, ₂₇钴:1, ₂₈镍:1, ₃₀锌:1, ₃₉钇:1, ₄₃锝:1, ₅₅铯:1, ₅₉镨:1, ₆₀钕:1, ₆₁钷:2, ₆₂钐:1, ₆₄钆:1, ₆₅铽:1, ₆₆镝:1, ₆₇钬:3, ₉₁镤:1
20	₁氢:3, ₉氟:1, ₁₂镁:1, ₁₄硅:2, ₁₅磷:1, ₁₇氯:3, ₁₈氩:1, ₁₉钾:3, ₂₀钙:2, ₂₄铬:2, ₂₅锰:1, ₂₆铁:1, ₂₇钴:2, ₂₉铜:1, ₃₀锌:2, ₃₈锶:1, ₄₂钼:1, ₅₄氙:1, ₅₈铈:1, ₅₉镨:1, ₆₀钕:2, ₆₁钷:1, ₆₃铕:1, ₆₄钆:1, ₆₅铽:1, ₆₆镝:3, ₆₇钬:1, ₉₀钍:1, ₉₂铀:1
……	……
99	₁氢:4691100944, ₂氦:165443203, ₃锂:215681190, ₄铍:115695809, ₅硼:150822242, ₆碳:196612989, ₇氮:256289758, ₈氧:334109221, ₉氟:435521299, ₁₀氖:567746714, ₁₁钠:740109987, ₁₂镁:963360027, ₁₃铝:1255875949, ₁₄硅:1637061009, ₁₅磷:761282011, ₁₆硫:992385048, ₁₇氯:1293649677, ₁₈氩:1686376168, ₁₉钾:2198310128, ₂₀钙:2865702632, ₂₁钪:475403674, ₂₂钛:619707840, ₂₃钒:807869353, ₂₄铬:1053079407, ₂₅锰:1372805933, ₂₆铁:1789538724, ₂₇钴:2332796196, ₂₈镍:708914937, ₂₉铜:924108976, ₃₀锌:1204656427, ₃₁镓:73988320, ₃₂锗:96469025, ₃₃砷:1392190, ₃₄硒:1815606, ₃₅溴:2365672, ₃₆氪:3085121, ₃₇铷:4020174, ₃₈锶:5242224, ₃₉钇:6832700, ₄₀锆:8906884, ₄₁铌:11611903, ₄₂钼:15135774, ₄₃锝:19730743, ₄₄钌:16815556, ₄₅铑:21915698, ₄₆钯:28573816, ₄₇银:37243811, ₄₈镉:48553385, ₄₉铟:63292574, ₅₀锡:82503511, ₅₁锑:107561269, ₅₂碲:140193810, ₅₃碘:182776636, ₅₄氙:238246907, ₅₅铯:310575027, ₅₆钡:404869781, ₅₇镧:527760537, ₅₈铈:687995253, ₅₉镨:896840060, ₆₀钕:1169110252, ₆₁钷:1524039042, ₆₂钐:787449908, ₆₃铕:1026527981, ₆₄钆:1107125354, ₆₅铽:1443203081, ₆₆镝:1881376627, ₆₇钬:2452457782, ₆₈铒:56140486, ₆₉铥:61583963, ₇₀镱:80267716, ₇₁镥:104644933, ₇₂铪:136410084, ₇₃钽:12370610, ₇₄钨:16129510, ₇₅铼:8650442, ₇₆锇:11278847, ₇₇铱:14701905, ₇₈铂:19164576, ₇₉金:24984156, ₈₀汞:32568011, ₈₁铊:42453401, ₈₂铅:55346940, ₈₃铋:72137420, ₈₄钋:94051424, ₈₅砹:122587668, ₈₆氡:159815386, ₈₇钫:208325443, ₈₈镭:271566398, ₈₉锕:354021423, ₉₀钍:387482170, ₉₁镤:505122669, ₉₂铀:5242224
100	₁氢:6115208888, ₂氦:215681190, ₃锂:281139012, ₄铍:150822242, ₅硼:196612989, ₆碳:256289758, ₇氮:334109221, ₈氧:435521299, ₉氟:567746714, ₁₀氖:740109987, ₁₁钠:964752217, ₁₂镁:1255875949, ₁₃铝:1637061009, ₁₄硅:2134087944, ₁₅磷:992385048, ₁₆硫:1293649677, ₁₇氯:1686376168, ₁₈氩:2198310128, ₁₉钾:2865702632, ₂₀钙:3735611106, ₂₁钪:619707840, ₂₂钛:807869353, ₂₃钒:1053079407, ₂₄铬:1372805933, ₂₅锰:1789538724, ₂₆铁:2332796196, ₂₇钴:3041023181, ₂₈镍:924108976, ₂₉铜:1204656427, ₃₀锌:1570353165, ₃₁镓:96469025, ₃₂锗:125738441, ₃₃砷:1815606, ₃₄硒:2365672, ₃₅溴:3085121, ₃₆氪:4020174, ₃₇铷:5242224, ₃₈锶:6832700, ₃₉钇:8906884, ₄₀锆:11611903, ₄₁铌:15135774, ₄₂钼:19730743, ₄₃锝:25722440, ₄₄钌:21915698, ₄₅铑:28573816, ₄₆钯:37243811, ₄₇银:48553385, ₄₈镉:63292574, ₄₉铟:82503511, ₅₀锡:107561269, ₅₁锑:140193810, ₅₂碲:182776636, ₅₃碘:238246907, ₅₄氙:310575027, ₅₅铯:404869781, ₅₆钡:527760537, ₅₇镧:687995253, ₅₈铈:896840060, ₅₉镨:1169110252, ₆₀钕:1524039042, ₆₁钷:1986649110, ₆₂钐:1026527981, ₆₃铕:1338123040, ₆₄钆:1443203081, ₆₅铽:1881376627, ₆₆镝:2452457782, ₆₇钬:3197005997, ₆₈铒:73195866, ₆₉铥:80267716, ₇₀镱:104644933, ₇₁镥:136410084, ₇₂铪:177813813, ₇₃钽:16129510, ₇₄钨:21021052, ₇₅铼:11278847, ₇₆锇:14701905, ₇₇铱:19164576, ₇₈铂:24984156, ₇₉金:32568011, ₈₀汞:42453401, ₈₁铊:55346940, ₈₂铅:72137420, ₈₃铋:94051424, ₈₄钋:122587668, ₈₅砹:159815386, ₈₆氡:208325443, ₈₇钫:271566398, ₈₈镭:354021423, ₈₉锕:461470490, ₉₀钍:505122669, ₉₁镤:658459711, ₉₂铀:6832700

接下来当然就很简单了，统计一下每种元素里“1”，“2”和“3”的数量，乘以化合物中此种元素的数量，再分别相加，就得到了化合物中“1”，“2”和“3”的数量。计算的结果是，第100项有511247092564个数字，其中有253103530928个”1”，63796211233个”2”和94347350403个”3”。“1”，“2”和“3”在此项中的比例大约分别是49.507084658%，32.038560926%和18.454354416%。（上面这三个百分比相加不严格等于100％，因为分别有尾数的四舍五入。下同。）注意到这个结果和我们上面粗略的估计千亿这个数量级是相符的。

对第100项可以这样算，对第1000000项也同样可以这样算，没有什么原则上的不同。只是对第1000000项来说，其中所含的元素数量实在太多，如果在编程时使用普通的32位或64位甚至128位的整数类形来表示是远远不够的，必须使用支持任意长度整数的数据类型，比如Java语言中的BigInteger。不过在此无法将这些数字具体写出来：第1000000项的长度以十进制数表示出来的话会有115137位，写出来将是一本中篇小说的篇幅。“1”，“2”和“3”的数量也一样无法具体写出，它们在此项中的比例分别约为49.507077868%，32.038585700%和18.454336321%。

看来当项数比较大时，“1”，“2”和“3”在数字串中的比例会趋向定值。这其实是算术引理的推论。因为随着项数趋于无穷，各元素在数字串中的比例趋近于它的丰度。以每种元素中“1”，“2”和“3”的数目乘以它的丰度，再分别相加能得到三个数字a，b和c，将它们归一化操作（即分别除以a+b+c）后就得到了当项数趋于无穷时“1”，“2”和“3”的比例的理论值，结果是约49.507077857%，32.038585734%和18.454336411%，和上面的结果相符。

我们可以问，为什么上面使用的计算长度的方法要比直接产生此项数字串再统计其长度的暴力法的计算速度快得多。因为在这种方法中，元素之间的顺序这个信息被省略而不参与计算。在前面的表中，我们只知道每一项化合物中每种元素有多少，但不知道它们分别处于化合物的什么位置。依照化学中表示物质组成的化学式来作比方的话，直接产生某项数字串类似于要知道物质的结构式，而上面的计算则只是得到了物质的实验式。而我们要知道数字串的长度或是其中“1”，“2”和“3”的数量，却恰恰并不需要知道元素之间的顺序。

七、具体的应用：第1000000项的某位数字

前面一节中的计算因省略计算元素之间的信息而变得迅速，但康威的理论也同样能帮助我们快速地知道，以1开始的边说边看序列的某项数字串的某个具体位置的数字是什么。

比如我们可以计算出，序列的第1000000项是以“132113213221133112”开始的。这我们甚至可以用手算：它的第8项以₇₂铪开头，于是第9项以₇₁镥开头，然后依次以₇₀镱，₆₉铥，₆₈铒，₆₇钬，₆₆镝，₆₅铽开头，第16项又以₆₇钬开头，我们发现了₆₇钬→₆₆镝→₆₅铽→₆₇钬……这个循环，所以此后所有3n的项都以₆₅铽开头，3n+1的项都以₆₇钬开头，3n+2的项都以₆₆镝开头，于是第999999项以₆₅铽开头，而第1000000项以₆₅铽一天后的衰变物，也就是₆₇钬₆₄钆开头。要计算第1000000项是以什么结尾的可用类似办法。这其实是起首引理和结尾引理的推论。

任意给定自然数n，要计算第1000000项数字串的第n位是什么数字则比较麻烦一点，但原则上来说也不难，当然一般不能用手算。序列在第8项演化成₇₂铪₅₀锡。而按照前面的方法，我们可以精确计算₇₂铪演化1000000-8=999992天后产生的化合物的长度d；如果d大于等于n，那么原问题就转化为₇₂铪演化999992天后数字串第n位是什么数字，反之则转化为₅₀锡演化999992天后数字串第n-d位数字是什么。这种方法可以一直继续下去直到求出结果：当化合物中有超过一个元素时，我们求出第一个元素最终产物的长度，以便知道我们感兴趣的那一位数字是否由它产生，如果不是，则可以抛弃这个元素（并修正所求数字所在的位数）；当化合物中只有一个元素，则将其代换为它一天后的衰变物，再重复这个步骤。

上面的算法的具体实现则需要一点技巧，因为单独一次计算某元素在若干天后产物的长度虽然并不耗时，但如果每次使用都需要重新计算的话，所用的总时间也是惊人的。所以可以预先计算，要用时再查表。可是如果所有计算结果都储存的话，需要的空间相当大（大概超过2To）。笔者采用折衷的方式，储存每隔1000天的结果，将所需空间削减为原需的千分之一，中间结果则在需要时再当场计算填充。具体的程序实现属于编程和算法问题，在此就不详细介绍了。在一台并不很新的个人电脑上，笔者的程序用大约20分钟生成上面所说的元素产物长度表格，每回答一个“第1000000项数字串中间第n位是什么”的问题则需要大约10分钟。计算结果：序列从第10⁴⁰⁰⁰⁰位开始的几个数字是3222112，它其实是一个₃锂元素的结尾部分；第10⁹⁰⁰⁰⁰位开始的几个数字是312，它其实是一个₃钒元素的结尾部分。

参考文献：

[1] John Horton Conway, The weird and wonderful chemistry of audioactive decay, Eureka 46:5-16 (1985); reprinted in Open Problems in Communication and Computation, T.M. Cover & B. Gopinath, eds., Springer-Verlag, New York, 173–188 (1987).