奇妙的心电图数列

心电图数列 (EKG Sequence) 的定义简单而有趣：第一项为 1 ，第二项为 2 ，以后的每一项都是最小的和前一项不互质并且不曾出现过的数。换句话说，数列 a(1)=1 ， a(2)=2 ，且当 n>2 时取 a(n) 为所有满足以下两个条件的数中最小的那一个：该数与 a(n-1) 有大于 1 的公约数，并且该数与前面 n-1 项都不相等。心电图数列的前面 20 项为

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 …

为什么它叫做心电图数列呢？原因很简单——因为把它描绘在图象上时，看上去像一张心电图。

心电图数列有很多有趣的性质。例如，考虑某个素数 p ，如果数列中第一个能被 p 整除的数是 t·p ，那么 t 一定就是前一项的因子了。由于 t·p 满足最小性，因此我们可以进一步得出， t 是 t·p 前一项的最小素因子。我们还可以推算出 t·p 的后一项。 t·p 的后一项要么就是 p ，要么就是（比 p 小的） t 的倍数。但后者是不可能，如果存在某个 t 的倍数比 p 小而之前又没出现过，那 t·p 这一项本身就不会是 t·p 了，而将由这个 t 的倍数取代。因此， t·p 的后一项一定是 p 。我们还可以看出，只要 t≠2 ，这个 p 的后一项就一定是 2p ；而当 t=2 时， p 的后一项就只能是 3p 了。也就是说，如果数列中出现了一个素数 p ，那么 2p 不是它的前一项就一定是它的后一项。

有意思的是，除了 p=2 以外，目前我们还没有找到 2p 出现在 p 后面的情况。换句话说，人们发现，对于数列中的每个奇素数 p ，它的前一项无一例外地都是 2p ，并且后一项总是跟着 3p 。证明或推翻这个猜想并不容易，直到最近几年才出现有关它的证明。很大程度上来说，这是整个数列呈心电图模样的最关键原因。

心电图数列有一个很漂亮的数学事实：所有的自然数都出现在了这个数列中。由这个数列的定义，每个数最多也只能出现一次。因此，心电图数列是全体自然数的一个排列。这个结论的证明堪称经典。首先我们证明引理 1 ：如果数列中有无穷多项都是某个素数 p 的倍数，那么 p 的任意一个倍数都出现在了数列中。证明的基本思路是反证。无妨假定 k·p 是最小的不在数列中的 p 的倍数。我们总能找到一个充分大的 N ，使得从第 N 项开始所有数都不小于 k·p 。然而数列中有无穷多项都是 p 的倍数，因此在第 N 项后面一定能找到一个 p 的倍数，这个数的下一项就只可能是 k·p 了，矛盾。

我们可以故技重施，继续证明引理 2 ：如果某个素数 p 的任意一个倍数都出现在了数列中，那么所有正整数都出现在了数列中。反证，假设 k 是最小的不在数列中的数，我们总能找到一个充分大的 N ，使得从第 N 项起后面的所有数都不小于 k 。由于素数 p 的任一倍数都在数列里，因此 k·p 的任一倍数都在数列里，即数列中有无穷多项都是 k 的倍数。那么，第 N 项之后一定存在一个 k 的倍数，它的下一项就只可能是 k 了，矛盾。

接下来就是最妙的地方了。我们可以利用上面两个引理立即得知，所有正整数都出现在了数列中。假设数列中所有项的所有素因子只有有限多种，但整个数列有无穷多个数，因此至少有一种素因子出现了无穷多次，由引理 1 可知这个素因子的所有倍数都在数列里，由引理 2 所有数都出现在了数列中，与前面的假设矛盾。因此，数列中包含有无穷多种素因子。而前面说过，数列中第一个含有素因子 p 的项，其下一项一定是素数 p 。因此，数列中出现了无穷多个素数。而素数 p 的前一项或者后一项必有一个是 2p ，因此素因子 2 出现了无数多次。由引理 1 可知 2 的所有倍数都在数列里。由引理 2 可知所有数都在数列中了。

心电图数列还有很多优美的性质和尚未解决的猜想。把前面 500 多个数描绘在图象上，容易看出整个图象大致成三条斜线，其中两条稀疏的线明显是由形如 p 和 3p 的数组成。于是有人猜想，如果把所有 p 和 3p 都变成 2p ，整个数列在渐近意义上与 f(n)=n 等价。

由此我们又想到一个问题，既然 a(n) 与 n 相差不远，那么它们之间的大小关系究竟如何？作出 a(n)-n 的图象，我们立即得出一个新的猜想：排除 a(n) 为素数的情况，则几乎所有 a(n) 都大于 n 。

从这里(http://www.research.att.com/~njas/sequences/A064413)看来，这两个问题中，前一个问题似乎已经得到了证明，后一问题则是最近才提出的猜想，还有待人们继续探索。