The 3x + 1 class record search - “3x+1问题”- 项目介绍

碧城仙

关于“3x+1问题”的详细介绍见于——《三思科学》电子杂志，创刊号，2001.07.01
下文转自：http://www.oursci.org/magazine/200107/010714.htm
感谢 三思科学网站 和文章作者 异调 ！


3x+1问题
                           　　　 作者：异调  


一、一个简单的问题

当我们阅读数学史时，会有这样一种印象，数学家们首先研究简单的问题，然后研究越来越复杂的问题。经常性地，高深的数学问题是非常复杂的。只是为了理解问题，我们就得学习非常多的数学知识；而为了解决它，那就得用更复杂的数学知识了。就算我们在学校里的数学考试也是如此，最后一题经常被叫做“最后一大题”，“一大题”是说它表达复杂，里面还有一二三四的小题，要理解题意就得几分钟的时间。弄不好还理解错了，搞得整道题都白白做，被扣去许多分。

可是数学里不只有这些吓人的“大题”——我是说，数学里还有吓人的“小题”。这样的“小题”理解起来非常容易，却让无数数学家大跌眼镜，怎么冥思苦想也不得其解。3x+1问题大概就是其中最著名而又最简单的一个。它简单到大概任何一个会除2和会乘3的人（比如说，没文化但是经常买菜的老奶奶）都能理解它的意思，但是困难得让数学家至今也没有找到好好对付它的方法。

任取一个自然数，如果它是偶数，我们就把它除以2，如果它是奇数，我们就把它乘3再加上1。在这样一个变换下，我们就得到了一个新的自然数。如果反复使用这个变换，我们就会得到一串自然数。

比如说我们先取5，首先我们得到3*5+1=16，然后是16/2=8，接下去是4，2和1，由1我们又得到4，于是我们就陷在4→2→1这个循环中了。

再举个例子，最开始的数取7，我们得到下面的序列：7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1这次复杂了一点，但是我们最终还是陷在4→2→1这个循环中。

随便取一个其他的自然数，对它进行这一系列的变换，或迟或早，你总会掉到4→2→1这个循环中，或者说，你总会得到1。已经有人对所有小于100*(2^50)=112589990684262400的自然数进行验算，无一例外。

那么，是否对于所有的自然数都是如此呢？

这看起来是个多么简单的问题啊！


二、克格勃的阴谋？

这个问题大约是在二十世纪五十年代被提出来的。在西方它常被称为西拉古斯(Syracuse)猜想，因为据说这个问题首先是在美国的西拉古斯大学被研究的；而在东方，这个问题由将它带到日本的日本数学家角谷静夫的名字命名，被称作角谷猜想。除此之外它还有着一大堆其他各种各样的名字，大概都和研究和传播它的数学家或者地点有关的：克拉兹(Collatz)问题，哈斯(Hasse)算法问题，乌拉姆(Ulam)问题等等。今天在数学文献里，大家就简单地把它称作“3x+1问题”。

角谷静夫在谈到这个猜想的历史时讲：“一个月里，耶鲁大学的所有人都着力于解决这个问题，毫无结果。同样的事情好象也在芝加哥大学发生了。有人猜想，这个问题是苏联克格勃的阴谋，目的是要阻碍美国数学的发展。”不过我对克格勃有如此远大的数学眼光表示怀疑。这种形式如此简单，解决起来却又如此困难的问题，实在是可遇而不可求。

数学家们已经发表了不少篇严肃的关于3x+1问题的数论论文，对这个问题进行了各方面的探讨，在后面我会对这些进展作一些介绍。可是这个问题的本身始终没有被解决，我们还是不知道，“到底是不是总会得到1？”

在1996年B. Thwaites悬赏1100英镑来解决这个问题。我写一下这个悬赏的文献：Thwaites, B. “Two Conjectures, or How to win ￡1100.”Math.Gaz. 80, 35-36, 1996，好在大家万一证出来时知道跑哪里去领奖。看在钱大爷的份上，3x+1问题于是又多了个名字，叫Thwaites猜想。

要是真的有这么一个自然数，对它反复作上面所说的变换，而我们永远也得不到1，那只可能有两种情况。

1)它掉到另一个有别于4→2→1的循环中去了。我们在后面可以看到，要是真存在这种情况，这样一个循环中的数字，和这个循环的长度，都会是非常巨大的；
2)不存在循环。也就是说，每次变换的结果都和以前所得到的所有结果不同。这样我们得到的结果就会越来越大（当然其中也有可能有暂时减小的现象，但是总趋势是所得的结果趋向无穷大）。

因为这是个形式上很简单的问题，要理解这个问题所需要的知识不超过小学三年级的水平，所以每一个数学爱好者都可以来碰碰运气，试试是不是能证明它。不过在这里我要提醒大家的是，已经有无数数学家和数学爱好者尝试过，其中不乏天才和世界上第一流的数学家，他们都没有成功。如果你在几小时内就找到了一个“证明”，那么把它一步一步地严格地写下来，看看是不是严密正确（我可以肯定它是错的，我这样的肯定要冒的危险绝不超过连续中十次彩票头奖的概率，既然我不买彩票，我就没道理不这么肯定:-)）。事实上，在互联网上已经有一些错误的“证明”。据说还有个数学爱好者跑到公证处去公证他的“证明”，生怕别人把他的好主意偷跑了。

二十多年前，有人向伟大的数论学家保尔·厄尔多斯(Paul Erdos)介绍了这个问题，并且问他怎么看待现代数学对这问题无能为力的现象，厄尔多斯回答说：“数学还没有准备好来回答这样的问题。”


三、一些概念，一些纪录

虽然证不出猜想，但是数学家们还是得到了许多很可能很有用的结论。让我们先来定义几个概念，然后再来介绍这些结论。

从一个自然数开始，用上面这个变换，我们可以计算出一串自然数的序列。为了形象起见，我们把这串数列叫做以最初用来开始计算的那个自然数命名的“航班”。
比如说，第6次航班就是 6→3→10→5→16→8→4→2→1
我们把一个航班里的最大数字，叫做这个航班的“最大飞行高度”。比如说，第6次航班的最大飞行高度就是16。我们把航班在数字1“着陆”之前的数字个数（最初的数字包含在内，但1不包含在内），叫做这个航班的“航程”（特别定义第1次航班的航程为0）。第6次航班的航程就是8。如果真有自然数在此变换下永远达不到1，那么这个航班的航程就是无穷了。

接下去的概念稍微有点复杂。我们把从起点开始（但不包括起点）连续的不小于起点的数字的个数，叫作“保持高度航程”。举一个例子来说明这个概念比较方便：
第11次航班是 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
我们看到从起点开始，34，17，52，26，13，40，20都不小于起点11，共有7个数字，所以第11次航班的保持高度航程为7。后面的航程中虽然还有数字16大于起始点11，但是它不被算在保持高度航程里了。一个最简单的推论就是，偶数次航班的保持高度航程总是0，因为开始就除以2，跌到较低的高度去了。

为什么我们对一个航班的保持高度航程感兴趣？因为如果所有航班的保持高度航程都是有限的话，3x+1问题就成立了。让我们假设已知所有航班的保持高度航程都是有限的，用数学归纳法来证明3x+1问题，也就是所有的航班都在1上“着陆”。我们已经知道第1到第5航班都是在1上着陆的，现在假设对于所有小于n的数字k，第k次航班都在1上着陆，我们来看看第n次航班的情况：由于按假设它的保持高度航程是有限的，所以它迟早会降落在一个比n小的数字上——于是按归纳假设它就会降落在1上！

我们可以对开始的30班航班列出一个相关数据表来：

航班  航程  保持高度航程  最大飞行高度
1      0         0               1
2      1         0               2
3      7         5              16
4      2         0               4
5      5         2              16
6      8         0              16
7     16        10              52
8      3         0               8
9     19         2              52
10      6         0              16
11     14         7              52
12      9         0              16
13      9         2              40
14     17         0              52
15     17        10             160
16      4         0              16
17     12         2              52
18     20         0              52
19     20         5              88
20      7         0              20
21      7         2              64
22     15         0              52
23     15         7             160
24     10         0              24
25     23         2              88
26     10         0              40
27    111        95            9232
28     18         0              52
29     18         2              88
30     18         0             160

下面要说说几个记录。在上面我们已经说过，目前3x+1问题已经被检验到100*(2^50)=112589990684262400，都没有发现反例。这是葡萄牙阿弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙的编程方法。他的主页在http://www.ieeta.pt/~tos/3x+1.html

如果一个航班的航程大于所有它前面的航班的航程，我们就把它叫作“航程纪录航班”，比方说第7航班，它的航程是16，比第1到6次航班的航程都长，所以第7航班是个航程纪录航班。今天我们已经知道的航程纪录航班有118个，航程最长的是2234047405400065次航班，它的航程是1871，这是Eric Roosendaal发现的，他有个个人网站http://personal.computrain.nl/eric/wondrous/，里面有各种各样关于3x+1问题的信息，下面的记录也都来自这个网站。

同样的，如果一个航班的保持高度航程大于所有它前面的航班的保持高度航程，我们就把它叫作“保持高度航程纪录航班”，比方说从上面的表中我们看到第7航班也是个保持高度航程纪录航班。今天已知的保持高度航程纪录航班有30个，航程最长是1008932249296231次航班，它的保持高度航程是1445。

最大飞行高度记录航班就是那些最大飞行高度记录大于所有它前面的航班的那些航班，现在已知的有76个，最大的是10709980568908647次航班，到达了350589187937078188831873920282244的高度。

对于一个固定航班N，考虑它在1着陆之前所作的变换，如果把其中除以2的变换称为“偶变换”并记为E(N)，而把乘以3再加1的变换称为“奇变换”并记为O(N)。数学家已经证明，O(N)/E(N)<log2/log3。我们注意到，对有些航班来说，O(N)/E(N)非常接近于log2/log3≈0.63092975……。有猜想认为它会越来越接近这个数字（也有相反的猜想，认为不会无限接近），所以大家为此设立了另一个纪录，就是这个比值比所有以前的航班更接近log2/log3的航班。这样的纪录不多，
现在已知的有15个，其中最后一个是N=100759293214567，I(N)/P(N)≈0.604938。值得一提的是N=104899295810901231，它的这个比值还要更靠近，达到0.605413，但是我们不知道它是否是一个纪录，也就是说，我们不知道所有比它小的航班里，是否还有比这个比值更靠近log2/log3的。

我们知道，对于任何p，总有至少一个航班，它的航程是p：2p→2p-1→2p-2→……→4→2→1
但是一般并不需要这么大的航班，就可以达到航程p。在2000年有人提出要找到最小的航班号，使得它的航程恰好是2000。现在最好的纪录是第67457283406188652次航班，但谁都不知道这是不是最小的航程为2000的航班。

计算一个航班的算法是非常简单的——只要除2或乘3加1。但是为了检验大量的和航次巨大的航班，巧妙的编程方法是非常重要的。上面的那些纪录都是由几台类似于我们平时使用的那样的计算机得到的结果。但是如果没有好好地思考和编程，光是硬算，那么使用最先进的计算机恐怕也得不到这样的结果。

为了验证一个航班的确在1上着陆，并不一定需要把结果计算到1。如果你已经验证了所有航次小于n的航班都在1上着陆，那么对于第n次航班，你只要把结果计算到一个小于n的数m就可以了——我们已经验证过第m次航班在1上着陆。事实上，如果我们只要计算到一个以前的航班飞行时到达过的数值就可以了，当然这需要记住以前已经到达过的比较高的高度，这里也必须巧妙地编程使得这样的记忆所使用的内存比较少。

更重要的是使用数学方法去减少计算量。比如说，任何n=4k+1的航班最终都会飞到一个比n更小的高度。首先这是奇数，我们乘3加1得到12k+4，然后连除两次2，就有3k+1<n。所以我们没有必要费功夫去验证4k+1型的航班。另外偶数次航班第一次变换就被除以2，降低了高度，所以同样也不需专门验证。只用这样一个小技巧，我们就使计算量减少到原来的25%。

如果按照这样的思路下去，我们同样不需要考虑16k+3型的航班，只要考虑到前面的飞行记录：
16k+3→48k+10→24k+5→72k+16→36k+8→18k+4→9k+2→……
而9k+2<16k+3。

我们可以这样追踪下去，考虑256k+i型的航班，其中i取0到255，那么我们会发现我们需要考虑的类型只有i=27、31、47、63、71、91、103、111、127、155、159、167、191、207、223、231、239、251、255。这样我们要作的计算只有最初的8%不到。

而Eric Roosendaal得到上面那些纪录的程序，是建立在对65536k+i型航班分析的基础上的，其中只有1729种航班需要真正的检验（只有原来计算量的2.6%）。他的程序还使用了其它的算术技巧，以及可以同时计算好几个航班。Tomas Oliveira e Silva进一步改进了这些技巧，从而使得他成为现在3x+1问题验证的世界纪录保持者（他的计算从1996年8月开始，到2000年4月结束，其间使用了两台133MHz和两台266MHz的DEC Alpha计算机）。Eric Roosendaal还在和其他人一起合作进行计算（包括再次验证以前的结果），如果你愿意加入这个研究项目的话，可以去访问上面给出的他的主页。


四、理论结果

只要稍微动一下脑筋，我们就知道3x+1问题和下面几个命题都是等价的：
1)所有的航班的航程都有限；
2)所有的航班的保持高度航程都有限；
3)所有的航班中的偶变换的次数都有限；
4)所有的航班中的奇变换的次数都有限；
5)所有的航班的保持高度航程中偶变换的次数都有限；
5)所有的航班的保持高度航程中奇变换的次数都有限。

R. Terra和C. Everett证明了，“几乎所有的航班都会下降到它的起始点以下”，也就是说“几乎所有的航班的保持高度航程都有限”。
这里的“几乎所有”是有确定的数学意义的，它是指：

——存在一个自然数n1，在所有小于n1的航班里，最多只可能有1/10的航班，它们的保持高度航程无限；
——存在一个自然数n2，它比上面的n1要大，在所有小于n2的航班里，最多只可能有1/100的航班，它们的保持高度航程无限；
——存在一个自然数n3，它比上面的n2要大，在所有小于n3的航班里，最多只可能有1/1000的航班，它们的保持高度航程无限；
——等等等等……

这好象很接近证明“所有的航班的保持高度航程都有限”了，于是很接近证明猜想本身了。但是好好想想，这个结论只不过是说明保持高度航程无限的航班会越来越稀少罢了，它们还是有可能存在的……更糟糕的是，这个结论一点也没有排除有其它循环存在的可能。

对于在1上着陆的航班，数学家们也得到了一些结果。他们证明了，存在一个常数c，当n足够大的时候，在比n小的航班中，能够在1上着陆的航班的个数大于等于nc。在1978年R. Crandal首先给出c=0.05，虽然小了点，但毕竟是开头一步；然后J. Sander给出c=0.3；在1989年I. Krasikov得到c=0.43；1993年G. Wirsching得到c=0.48；最后在1995年D. Applegate和J. Lagarias得到c=0.81。看起来我们越来越接近c=1这个最终目标了。可是我们不知道现在用来得到c的方法是否
还可以再用下去，就好象在试图征服哥德巴赫猜想的过程中，陈景润用来证明1+2的方法，似乎不能用来证明1+1了。

1995年的这个证明相当特殊。它使用了计算机程序来解一个十分巨大的方程组，所以这个证明不能用手工来验证。在论文中，我们看见的不是一个关于c=0.81的定理的证明，而是一个关于如何写出这个巨大方程组的说明，和由程序计算出来的结果，以及如何使用这些结果来解释c=0.81。其他的数学家如果想验证这个结果，必须首先看懂关于方程组的证明和那些解释，再按照里面的说明来写一个程序（很复杂的！），运行它，再看看结果是否和文章中的相同。目前四色定理的
证明也是如此，所以数学家对此很不满意。

还有一些结果是关于如果有其他不同于4→2→1的循环存在时，对这样的循环的性质的研究。R. Crandal和N. Yoneda在1978年证明，如果这样一个另外的循环存在的话，那么它的长度（就是在这个循环中数字的个数，比如说循环4→2→1的长度就是3）一定要大于275000。1993年这个体积增大到17087915，最近的结果是102225496。这些结果是通过分析包括我们前面提到的各种纪录得到的，所以这些结果我们还是不能完全通过手工来验证。我们看到，如果真有另外的循环存在的
话，那一定是非常非常巨大的！


五、启发式论证

数学中有一种叫“启发式”的论证方法，建立在估计和概率的手段上。比如说底下的论证方法就是这个类型的：

“每个数字要么是奇数要么是偶数，如果随便取一个自然数，碰到奇数和偶数的可能性是一样的。如果我们把一次航班中这一系列数值看作是随机的话，那么使用奇变换和偶变换的可能性也是一样的，所以平均在每两次变换中我们有一次是n→3n+1，有一次是n→n/2。所以平均起来，每次飞行高度的变化就是乘以3/2，于是……就会越飞越高。”

这样的启发式论证就推翻了原来的猜想！但是这个论证显然比较幼稚，因为它没有考虑到，每一次奇变换后随即而来的一定是一次偶变换，因为如果n是奇数的话，3n+1一定是偶数；而每一次偶变换后随即而来的却不一定是一次奇变换。J. Lagarias改进了这个启发式论证。他指出，如果我们把奇变换后再作偶变换考虑在一起，那么这样得到的结果可以看作是真的“很随机”。于是有1/2的可能性它是奇数，有1/4的可能性是一个奇数的2倍，有1/8的可能性是一个奇数的4倍，等等。于是飞行高度的变化就是以下变换的“平均效应”；

——n乘以3/2，这有1/2的可能（奇变换后再作偶变换的结果为奇数）；
——n乘以3/4，这有1/4的可能（奇变换后再作两次偶变换）；
——n乘以3/8，这有1/8的可能（奇变换后再作三次偶变换）；
…………

于是平均来讲，每次变换后高度的变化就是
c=(3/2)1/2(3/4)1/4(3/8)1/8(3/16)1/16……=3/4
所以高度在总体上来说应该是越来越低，每次大约低25%，最终降到一个循环上（不过这个论证没有排除有除了4→2→1以外的其他循环）。这个论证可以使我们使用论证中的模型来计算出，从一个自然数开始，平均要多少步的这样的飞行（就是保持高度航程中奇变换的次数），可以使飞行高度降到起始点以下。理论上的数值是3.49265……。如果我们对3到2000000000（二十亿）之间的航班的保持高度航程中奇变换的次数取平均值，我们得到3.4926……。这两个结果惊人的一致
性使我们相信上面的启发性模型是正确的。如果它是正确的，那么就意味着没有保持高度航程无限的航班，于是3x+1猜想就是正确的，至少可以得出没有飞得越来越高的航班的结论。

可是一个启发性论证，就算再有实验证据来表明它是对的，也只不过是个论证，只能使我们对猜想的正确性更充满信心。它不能代替真正的数学证明。比如说，数学家猜想在π的十进位小数表示当中，出现0到9各个数字的可能性是一样的，对π的数值计算也强烈支持这个猜想，可是如果没有数学证明，它还是得被叫做一个猜想，而不是定理。

用上面这个启发式的概率模型，我们还可以预言，对于第n次航班，它的最大飞行高度不会超过Kn2（对于某个常数K）。数值计算表明对于K=8，这个公式是正确的（同样地，这可以让我们提出猜想，而不是证
明定理）。


六、会不会永远证不出来？

自从哥德尔发表了他的著名的不完备性定理以来，每次碰到一个十分困难的问题时，数学家们就免不了疑神疑鬼——这会不会证不出来？

哥德尔的不完备性定理说，在包含皮亚诺的自然数公理的数学公理系统中，总有不可证明的命题存在。公理系统的这种性质叫不完备性。比如说，如果我们只取欧氏几何的前四条公理，那么平行公理是不能用这前四条公理证明出来的，也就是说只有前四条公理的平面几何是不完备的（这个例子不是很严格，因为欧几里德的公理系统在现代观点下是不严密的，但是我举这个例子只是为了说明不完备性这个概念，所以关系不大）。

所以说，如果我们只用皮亚诺的自然数公理，甚至再加上现代的集合论公理系统，也有可能不能证明3x+1问题。甚至即使3x+1猜想其实是错误的，我们也有可能不能证明这一点。比如说，我们可能发现一个航班，我们对它进行计算，发现它飞得越来越高，但是无论如何不能证明它永远也不会回到1上来。

当然无论什么数论问题都有可能搞得数学家们这样疑神疑鬼，虽然其实是他们还没有发现证明。不过有一些蛛丝马迹表明我们有必要稍微严肃点看待此问题，因为3x+1问题离不可证明的问题并不太远。

J. Conway（喜欢数学游戏的朋友可能会记起这个名字来，著名的生命游戏就是他发明的）在1972年考虑了3x+1问题的推广形式。在3x+1问题里，我们把数字除以2，然后得到了2种可能的余数（0或者1），按照余数我们使用2个公式（除以2或者乘3加1）。Conway考虑了除以一个固定的p，按照余数的不同（这时就有p种不同的余数）分别使用p个公式的情况。然后他提出了一个类似“在1着陆”的猜想。他在论文中证明了，这个猜想在集合论公理系统中是不可证的。

事实上，在任何一个包含了皮亚诺的自然数公理的数学公理系统中，Conway的方法都可以定义一个类似于3x+1问题的不可证命题。当然这不是说有一个在所有公理系统中都不可证的命题。“不可证”总是相对于某公理系统而言的。当然，Conway的方法并没有说明3x+1问题本身是不可证的，也没有说它一定是很困难的（事实上有些3x+1问题的变种是很容易解决的），但是这毕竟说明，有些很象3x+1问题的命题是不可证的，这把事情搞得很可疑。

1993年，法国里尔(Lille)的基础信息实验室使用了Conway的方法来演示一套基于逻辑规则的编程形式的威力。同许多数学中的例子一样，先头看上去最没用的课题，会有很具体的用处。


七、各种变种

数学家总喜欢把问题推广，使它更抽象化和一般化，因为这样可以把一种在具体某个问题上使用的方法的威力应用到一般的情况上去，从而得到很有可能是出乎意料的结论。

数学家们首先考虑，如果把3x+1问题的规则运用到负整数上去，会产生什么现象。他们发现了三个不同的循环：
1)-1→-2
2)-5→-14→-7→-20→-10
3)-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122
→-61→-182→-91→-272→-136→-68→-34
他们猜想，这就是所有的循环，而所有的负整数都会掉进其中一个里。

他们还提出了5x+1问题，也就是在奇数的情况下用5x+1来取代3x+1。
这下又有好几个循环：
1)6→3→16→8→4→2→1
2)13→66→33→166→83→416→208→104→52→26
3)17→86→43→216→108→54→27→136→68→34
但是5x+1问题中的第7次航班好象老在那里飞啊飞，怎么也跑不到一个循环里去，但是谁都不能证明的确如此。

上面Lagarias的那个启发式论证使得数学家猜想，如果q是大于3的奇数的话，对于qx+1问题，总存在至少一个航程无穷的航班，这看起来很象是一个“反3x+1问题”。

还有许多其他的3x+1问题的推广，一些结果把它们和其它数学领域联系起来，比如说素数理论，某些丢番图方程（求解系数为整数的方程的整数根，比如著名的费尔马大定理就是一个丢番图问题），马尔可夫链（概率论中的递归理论），遍历理论（一种关于函数混合递归的理论）。

就算3x+1问题终于被解决了，看看所有这些变种，也够数学家们自娱自乐上几百年的了。



　　　　http://www.ieeta.pt/~tos/3x+1.html
　　　　http://personal.computrain.nl/eric/wondrous/

碧城仙

简单的说这是一个连经常买菜的老奶奶都能理解其意思的问题，但是却困难得让数学家至今也能找到好好对付它的方法。

任取一个自然数，如果它是偶数，我们就把它除以2，如果它是奇数，我们就把它乘3再加上1。在这样一个变换下，我们就得到了一个新的自然数。如果反复使用这个变换，我们就会得到一串自然数。

数学里不只有些吓人的“大题”——我是说，数学里还有吓人的“小题”。这样的“小题”理解起来非常容易，却让无数数学家大跌眼镜，怎么冥思苦想也不得其解。3x+1问题大概就是其中最著名而又最简单的一个。它简单到大概任何一个会除2和会乘3的人（比如说，我们取数字5，那么3*5+1=16，然后是16/2=8，接下去是4，2和1，由1我们又得到4，于是我们就陷在4→2→1这个循环中了。

再举个例子，最开始的数取7，我们得到下面的序列：
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
这次复杂了一点，但是我们最终还是陷在4→2→1这个循环中。

随便取一个其他的自然数，对它进行这一系列的变换，或迟或早，你总会掉到4→2→1这个循环中，或者说，你总会得到1。已经有人对所有小于100*(2^50)=112589990684262400的自然数进行验算，无一例外。
========================================

互联网上早就有研究该问题的分布式计算项目——“The 3x + 1 class record search ”

英文介绍页面地址为：
http://distributedcomputing.info/ap-math.html#3xplus1
中文介绍页面地址为（暂时无法访问）：
http://www.equn.com/distributed/ap-math.html#3xplus1

英文介绍如下：
Find 3x+1 class records in the 3x+1 Problem project. This project attempts to find ever higher 3x+1 class records. The client, which will work on any PC/Windows platform, and the instructions for joining the project, are here. Note: the client takes about 6 weeks to finish one block on a 400-MHz CPU.

The project completed its first goal, processing 20,000 blocks, on November 19, 2002. The project found a new glide record in December, 2002. This is the first glide record found in almost a year. The record occurs at 180352,746940,718527, and the new glide is 1575, an improvement of 104 over the previous record. The project found a new Path record in March, 2003. The previous Path record was found in late 2002. The record occurs at 212581,558780,141311, (or +/- 189.250) and it reaches a maximum of 4353,436332,008631,522202,821543,171376.

中文翻译如下：（如有错误，敬请指正！谢谢！）
在 3x+1 class records 网站（ http://personal.computrain.nl/eric/wondrous/ ）可以查看 3x +1 问题现今业已发现的各类组合。该项目试图帮助数学家们寻找到更过数值较高的3x +1 组合。您可以在 http://personal.computrain.nl/eric/wondrous/search.html 页面下载到一个客户端程序，它可以在任何PC机/Windows平台下工作。
请注意：如果您使用一个400-MHz的CPU，完成一个WU周期的计算将花费您接近6周的时间。

该项目在2002年11月19日完成了它的第一个目标，共计处理了20，000个测试组合。该项目在2002年12月发现一个新的组合（详见：http://personal.computrain.nl/eric/wondrous/glidrecs.html ）。这是第一个几乎花费了整整一年时间才发现的组合。该组合在180352，746940，718527作为测试对象时被发现，新的目标定为1575，该目标是基于此前的104组合的改进。该项目在2003年3月发现了一个新的组合（详见：http://personal.computrain.nl/eric/wondrous/pathrecs.html ）。 以前的组合都是在2002年后期被发现的。那些组合是在对212581，558780，141311(或者+/-（189.2）^50)以及最大大到4353,436332,008631,522202, 821543,171376等数值作测试对象时发现的。

您可以在 http://personal.computrain.nl/eric/wondrous/progress.html 查看到项目的最新进展。
========================================

该分布式计算项目的名称为 3x+1 Problem ( The 3x + 1 class record search )


官方网站为 http://personal.computrain.nl/eric/wondrous/

您可以从 http://personal.computrain.nl/eric/wondrous/search.zip 下载一个仅仅只有15KB的程序利用您的电脑的闲置处理能力帮助数学家们寻找更多的 3x + 1 组合。其工作原理和互联网上最大的分布式协同计算项目——“SETI@home”（在家寻找外星智慧文明）——类似。


碧城仙2005年10月补充：
请注意：官方站点更换了域名，请访问 http://www.ericr.nl/wondrous/index.html 或者 http://ericr.nl/wondrous/
客户端下载地址： http://ericr.nl/wondrous/search.zip
项目指南：http://ericr.nl/wondrous/search.html   

碧城仙

项目英文详细说明如下：（转自安装包内文件 info.txt ）

How do I get a block?
=====================
Currently searches are performed in 'blocks' of 20e+12.
You get a block assigned to you by emailing the author at
[email protected]


How long will a single block take?
==================================
On a medium fast (these days) PC of 400 MHz it will take 5-6 weeks.
Whenever a new block is started the script will show you a message
with a fairly accurate estimation of how long a block will take to finish.
This is, of course, assuming no other heavy calculation processes run
at the same time.


How do I start the block search?
================================
Simply edit the third line of .vbs file to specify your block.
If you use an interval of 20 then that's all. If you decide to
divide the block between several machines you change the next line as well.


How to run the program without Script Host
==========================================
The trick is that it can be run from the command line, like this:

start /low w422b /o /c233 /fn2645.log 2645,456,000,000,000

This is what this means:

/low: start on idle time. This ensures the program is not slowing down your system.

/o : optimized run. This is to verify the program is started properly and not accidentally

/c<number> : (optional) the number of loops. Each loop is 2^32, or almost 4,300,000,000.
233 loops is just about 1e+12, you can use bigger numbers as well of course.
If you do not specify a count the program will run "forever".

/f<filename> : (optional) filename in which to log the result.
If no filename is specified it will use 'wondrous.log'.

<number>: the number to start with. This is automatically rounded down to a multiple of 2^32, so the last 9 digits are not very important usually. The comma's are optional, and help to make it more readable.


The results from the run
========================
The program writes a log file entry every 4 loops, and when it starts or finishes.
It also logs every interesting number. There are not many interesting numbers
at these big numbers, just about one in every 5 e+12, and sometimes they come
in groups as well, so it is not at all strange if you search for a week
and find (almost) nothing. The program also writes the time and the number
of overflows found. This last number enables a check on whether results are
correct and reproducible. Note that no floating point math is involved,
so the program is not affected by the infamous pentium bug.


Reporting
=========
The idea is that once the block is finished you mail the logfile to
[email protected]
It's usually not very big (~70kB), and of course you can use winzip to make it even smaller.

碧城仙

我怎样获得一个计算任务块？
=====================
目前正在搜寻计算以“20e +12”为中心的数据任务块。
您能够通过发送电子邮件给本程序作者（[email protected]）来获得一个计算任务块。


一个单个的计算任务块大概要处理多久？
==================================
如果在一台 CPU 主频为 400 MHz 的PC上运行将需要花费5-6个星期。当一个新的数据块开始测试时，程序脚本将会弹出一个消息框，这也是基于对您的尊重，消息框将提示当前数据包完全计算完毕所需要的时间，以便让您随时掌握程序计算的动向。当然，如果您的计算机同时在运行其他繁重的演算过程，请暂时不要运行本程序。


我怎样开始寻找并测试所需的数据块？
================================
可以很简单的编辑 search.vbs 文件的第3行，将您通过电子邮件从程序作者处获得的计算任务块数字指向“Const blockstart”；您也可以设置每测试完20个块显示一次计算进度。如果你同时采用几台计算机来计算，可以分别在这几台机器之间分块，那么您也必须对 search.vbs 文件的第3行做修改。
以下是 search.vbs 文件的前六行内容：
option explicit

' ---- Change this constant for a new block! ----
Const blockstart = 12860
Const blockinterval = 20
' --------------------------------------


怎样在没有控制脚本的情况下运行程序？
==========================================
这就有个窍门了，您可以将程序从命令行状态下开始运行（即是说运行需要通过 cmd.exe - 命令行解释器），例如：

start /low w422b /o /c233 /fn2645.log 2645,456,000,000,000

参数说明：
/low : 设置程序运行的优先级，使程序只使用 CPU 的闲置处理资源。这一参数可以保证您的系统不因本程序而变慢。

/o : 最佳状态运转。这个参数将确保程序从正确的数据块开始测试而不随机的开始。

/c<number> : (该参数可选)循环的次数。每次循环的计算量都是2 ^ 32，或者说将近4，300，000，000。
233次循环差不多是1e +12，当然，您可以使用更大的数目。如果你不指定c后面的数目，那么程序将“永远”循环下去。

/f<filename> : (该参数可选)指定日志记录文件的文件名。如果没有文件名被指定，程序将默认使用“wondrous.log”。

<number>: 开始测试的数目。该参数将使程序自动从 2^32 的整数倍处开始，因此最后的9位数字通常并不重要。该参数设定的数字表示中的逗号的是可选的，其目的是增加可读性。


程序运行的结果
========================
程序运行过程中，每经过4次循环，将自动写入一次日志文件，当程序开始或结束时也会自动写入一次日志文件。它将记录下程序计算过程中出现的一切有趣的数字。 在一些大的数目范围内并没有多少有趣的数目，仅仅只在每个 5e+12 小范围内出现，有时，他们也有可能成群结队的来了，或者您寻找了一周却什么也没找到，这些都不奇怪。日志文件也将记录出现各种情况的时间和溢出数。最后的数字将表明结果是否正确。您将注意到本程序不涉及到浮点计算，所以 pentium CPU 设计上的缺陷不会影响程序的运行。


向官方报告计算结果
========================
当任务块计算完成以后请您将您的日志文件（logfile）通过电子邮件发送给我们（[email protected]） 。该日志文件通常都不会很大（约为70kB），当然，您可以通过使用 winzip 让它更小。


翻译人：碧城仙，版权为中国分布式计算总站所有。
========================
碧城仙   2006年1月1日补充

请注意，官方目前更换了邮件地址，想参加项目的朋友请看下面：

发送地址：[email protected]
邮件主题必须填写：3x+1_block_request

请注意，如果是想参加计算，邮件主题必须填写成“3x+1_block_request”！
如果想提问题或者联系些其他与项目有关的事情，邮件主题请填写“3x+1 search”。

wenmao

新地址 http://www.ericr.nl/wondrous/index.html

hackerboy

我初中时上课无聊，用文曲星编成算这个问题的反例，花了4个小时算到5000000位也没找到，之后文曲星就没电了。
现在想想还真是有趣呀~~

coolguy1983

当拷机软件也不错啊

碧城仙

请注意，官方目前更换了邮件地址，想参加项目的朋友请看下面：

发送地址：[email protected]
邮件主题必须填写：3x+1_block_request

请注意，如果是想参加计算，邮件主题必须填写成“3x+1_block_request”！

如果想提问题或者联系些其他与项目有关的事情，邮件主题请填写“3x+1 search”。

refla

我想问一下，3x+1项目关闭了，是否已经有结果了？

它的后继项目 Collatz Conjecture 又是怎么回事？

fwjmath

没有结束，还在运行，我的一个同学就正在算这个~~~
Collatz Conjecture这个项目是独立的，与这个项目的研究目的是不一样的~~~

aquarius12

请问3X+1 和 Collatz Conjecture的不一样的地方在哪里呢？

fwjmath

3x+1寻找的是步数分类记录，collatz寻找的是滑翔记录~~~
可以看：http://www.equn.com/3x+1

refla

回复 12# fwjmath

为什么当初不一起记录呢？现在又单独算，会不会“浪费”了点？

我这个是外行问的问题，你别见笑

fwjmath

回复 13# refla

因为这两个记录寻找的速度是不同的~~~
滑翔记录可以通过文中所说的筛法来去掉非常大一部分的数，而步数分类记录由于要对每个步数都找到，所以去掉的数就远远少于前者，这就直接导致了速度的不同~~~

海里游

我想问一下参加3X+1的项目到底运行什么？是分配给每个人比较大的数看是不是能进入4-2-1的循环？那数有多大？我用我和程序运行2^2048+1出现循环数字1的次数是15291，也就是前面所说的航程，时间也不到20秒。
他们都是些啥任务，是测试航程，还是找保持高度航程为几，还是测试能不能出现4-2-1循环？我的程序没设置保持高度航程，这个重要吗？下面贴出几个航程有特点的数字。
括号内是已知数字运行到1的次数(即：航程)
2^63-1=9223372036854775807 (862次)
2^62-1=4611686018427387903(861次)
2^61-1=2305843009213693951（860）
2^60-1=1152921504606846975（859）
2^59-1=576460752303423487（858）
2^58-1=288230376151711743（857）
2^57-1=144115188075855871（856）
2^56-1=72057594037927935（599）
2^55-1=36028797018963967（598）
2^54-1=18014398509481983（853）这个数的次数接前三个数的次数
2^53-1=9007199254740991（852）
2^52-1=4503599627370495（595）这个数的次数接前三个数的次数以下还在这样的现象
2^51-1=2251799813685247（594）
2^50-1=1125899906842623（593）
2^49-1=562949953421311（592）
2^48-1=281474976710655（591）
2^47-1=140737488355327（590）
2^46-1=70368744177663（589）
2^45-1=35184372088831（588）
2^44-1=17592186044415（587）
2^43-1=8796093022207（586）
2^42-1=4398046511103（536）
2^41-1=2199023255551（535）
2^40-1=1099511627775（534）
2^39-1=549755813887（533）
2^38-1=274877906943（532）
2^37-1=137438953471（531）
2^36-1=68719476735（530）
2^35-1=34359738367（529）
2^34-1=17179869183（528）
2^33-1=8589934591（527）
2^32-1=4294967295（451）
2^31-1 = 2147483647（450）
2^30-1 = 1073741823（449）
2^29-1 = 536870911（446）
2^28-1 = 268435455（385）
2^27-1 = 134217727（384）
2^26-1 = 67108863（445）
2^25-1 =33554431（444）
2^24-1 =16777215（474）
2^23-1 =8388607（473）
2^22-1 =4194303（304）
2^21-1 =2097151（303）
2^20-1 =1048575（178）
2^19-1 = 524287（177）
2^18-1 = 262143（225）
2^17-1 = 131071（224）
2^16-1 = 65535（130）
2^15-1 = 32767（129）
2^14-1 = 16383（159）
2^13-1 = 8191（158）
2^12-1 = 4095（157）
2^11-1 = 2047（156）
2^10-1 = 1023（62）
2^9-1 = 511（61）
2^8-1 = 255（47）
2^7-1 = 127（46）
2^6-1 = 63（107）
2^5-1 = 31（106）
2^4-1 = 15（17）
2^3-1 = 7（16）
2^2-1 =3（7）
除最后一项，至少有两个数的次数相邻，至于次数变化出现的计算过程的变化，没有细研究。
类似2^63+1的形式也和前面的规律一样，
只是航程从482开始减少。
为了节省帖子的空间，没有把某一个数字的每个航程的数据帖出来。