主题：【文摘】【动脑筋】一道有意思的“小题”：3x+1问题（上） -- 1001n
看到一篇很有意思、文笔也很优秀的数学科普文章，跟大家一起分享一下，来个思维小体操：）
原文应该在三思网刊，但是我看到的被转载在
--------------------------------------------------------------------------
一、一个简单的问题
当我们阅读数学史时，会有这样一种印象，数学家们首先研究简单的问题，然后研究越来越复杂的问题。经常性地，高深的数学问题是非常复杂的。只是为了理解问题，我们就得学习非常多的数学知识；而为了解决它，那就得用更复杂的数学知识了。就算我们在学校里的数学考试也是如此，最后一题经常被叫做“最后一大题”，“一大题”是说它表达复杂，里面还有一二三四的小题，要理解题意就得几分钟的时间。弄不好还理解错了，搞得整道题都白白做，被扣去许多分。
可是数学里不只有这些吓人的“大题”――我是说，数学里还有吓人的“小题”。这样的“小题”理解起来非常容易，却让无数数学家大跌眼镜，怎么冥思苦想也不得其解。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*250=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*250=112589990684262400，都没有发现反例。这是葡萄牙阿弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙的编程方法。
如果一个航班的航程大于所有它前面的航班的航程，我们就把它叫作“航程纪录航班”，比方说第7航班，它的航程是16，比第1到6次航班的航程都长，所以第7航班是个航程纪录航班。今天我们已经知道的航程纪录航班有118个，航程最长的是2234047405400065次航班，它的航程是1871，这是Eric Roosendaal发现的，他有个个人网站里面有各种各样关于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问题终于被解决了，看看所有这些变种，也够数学家们自娱自乐上几百年的了。
这是该文后面附出的参考链接，里面收录了3x+1问题的研究进展，包括截至今年5月25日得到的结果。本来想一次搞过来，但是里面有图，不太好弄，还是给出原始链接大家自己看，或许更好：）
原文还给了个链接，大概时间太久，已经失效了，就是这个：
虽然不属于25个科学问题，但是觉得这文章讲述的思路还是挺有启发性的，就转来吧：）
每次听政治课无聊的时候，我就在下面随便找个数开算。别人还以为我在认真记笔记呢
老萨的坑深浅能看出来,反正跳进去再深可以爬出来,等多久就看老萨心情和闺女的尿布厚度.
1001n的坑貌似很浅,但跳进来才知道上当了!自己也在帮他往下挖,越来越深!看密码专题就让我得了失眠症...这次这个坑,我下定决心,不跳.
现学现卖...