奇妙的心电图数列
icon2 Brain Storm | icon4 2010-02-20 0:06| icon322 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    心电图数列 (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 。
    从这里看来，这两个问题中，前一个问题似乎已经得到了证明，后一问题则是最近才提出的猜想，还有待人们继续探索。

Posted in Brain Storm
Tags: , , , , ,
Trackback: http://www.matrix67.com/blog/archives/2839/trackback
我猜您可能还喜欢：

22 条回复

  • 楼层: 沙发 | 2010-02-20 0:15 | ppwwyyxx 说：

    证明很有意思。。
    第一次离大牛这么近。

  • 楼层: 板凳 | 2010-02-20 0:30 | zfy 说：

    哈哈,第一次这么靠前啊

  • 楼层: 地毯 | 2010-02-20 0:53 | morrowind 说：

    这心脏跳的，怕过了n之后会动脉爆裂哈

  • 楼层: 地板 | 2010-02-20 2:18 | TonyShaw 说：

    如此定义数列……

  • 楼层: 地下室 | 2010-02-20 8:31 | jingo 说：

    近距离...

  • 楼层: 地基 | 2010-02-20 8:48 | 6V 说：

    前排膜拜大牛~~
    Lie to me我看了漫画……很不错~~一直在追，现在已经是在小岛上玩抢椅子了~

  • 楼层: 地壳 | 2010-02-20 9:20 | anythingjixu 说：

    路过

  • 楼层: 地幔 | 2010-02-20 9:27 | cat 说：

    前排就座

  • 楼层: 地核 | 2010-02-20 10:05 | crazywong 说：

    什么叫做“在渐近意义上与f(n)=n等价”？

  • 楼层: 10楼 | 2010-02-20 10:09 | crazywong 说：

    是指在f(n)=n上下摆动么？

  • 楼层: 11楼 | 2010-02-20 11:49 | map 说：

    mark

  • 楼层: 12楼 | 2010-02-20 17:57 | imstupid 说：

    楼层: 10楼 | 2010-02-20 10:09 | crazywong 说：
    是指在f(n)=n上下摆动么？

    是不是说满足(f(n) != n)的点对于满足 f(n) == n 的点是高阶无穷小？

  • 楼层: 12a楼 | 2010-02-20 19:37 | aa 说：

    拜神牛

  • 楼层: 14楼 | 2010-02-20 20:47 | 超子 说：

    证明不错~

  • 楼层: 15楼 | 2010-02-20 23:29 | struldburg 说：

    后排就坐…

  • 楼层: 16楼 | 2010-02-21 20:57 | neo 说：

    我很好奇，楼主都是在哪里看到到的这么些的资料。可否透露一下？

  • 楼层: 17楼 | 2010-02-21 23:37 | neo 说：

    我很好奇，楼主是在哪里看到的这么些资料。可否透露一下？

  • 楼层: 18楼 | 2010-02-22 3:15 | 白左 说：

    GJ~

  • 楼层: 19楼 | 2010-02-22 12:03 | 小楠 说：

    16楼，博主在文章的最后一行写着“从这里看来”，那个“这里”可以链接到原资料。

  • 楼层: 20楼 | 2010-02-23 18:15 | neo 说：

    19楼，谢谢了！

  • 楼层: 21楼 | 2010-03-02 17:18 | LS-GH 说：

    我也第一次留言

  • 楼层: 22楼 | 2011-08-17 10:15 | trek jersey 说：

    有点看不懂！

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。