3x+1问题（2）zz(转载)

显示全部楼层 · 2021-1-29 12:51:26

【以下文字转载自AAIS讨论区】【原文由dionysus所发表】
发信人:yapollo(绿太阳*淡出~~不再放任*),信区:Science标题:3x+1问题（2）zz发信站:BBS水木清华站(SunAug1220:39:202001)
三、一些概念，一些纪录
虽然证不出猜想，但是数学家们还是得到了许多很可能很有用的结论。让我们先来定义几个概念，然后再来介绍这些结论。
从一个自然数开始，用上面这个变换，我们可以计算出一串自然数的序列。为了形象起见，我们把这串数列叫做以最初用来开始计算的那个自然数命名的“航班”。比如说，第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班航班列出一个相关数据表来：
航班航程保持高度航程最大飞行高度1001210237516420455216680167161052830891925210601611147521290161392401417052151710160164016171225218200521920588207020217264221505223157160241002425232882610040271119592322818052291828830180160
下面要说说几个记录。在上面我们已经说过，目前3x+1问题已经被检验到100*250=112589990684262400，都没有发现反例。这是葡萄牙阿弗罗(Aveiro)大学的TomasOliveiraeSilva的工作，用了很巧妙的编程方法。他的主页在http://www.ieeta.pt/~tos/3x+1.html
如果一个航班的航程大于所有它前面的航班的航程，我们就把它叫作“航程纪录航班”，比方说第7航班，它的航程是16，比第1到6次航班的航程都长，所以第7航班是个航程纪录航班。今天我们已经知道的航程纪录航班有118个，航程最长的是2234047405400065次航班，它的航程是1871，这是EricRoosendaal发现的，他有个个人网站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+1n。所以我们没有必要费功夫去验证4k+1型的航班。另外偶数次航班第一次变换就被除以2，降低了高度，所以同样也不需专门验证。只用这样一个小技巧，我们就使计算量减少到原来的25%。
如果按照这样的思路下去，我们同样不需要考虑16k+3型的航班，只要考虑到前面的飞行记录：16k+3→48k+10→24k+5→72k+16→36k+8→18k+4→9k+2→……而9k+216k+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%不到。
而EricRoosendaal得到上面那些纪录的程序，是建立在对65536k+i型航班分析的基础上的，其中只有1729种航班需要真正的检验（只有原来计算量的2.6%）。他的程序还使用了其它的算术技巧，以及可以同时计算好几个航班。TomasOliveiraeSilva进一步改进了这些技巧，从而使得他成为现在3x+1问题验证的世界纪录保持者（他的计算从1996年8月开始，到2000年4月结束，其间使用了两台133MHz和两台266MHz的DECAlpha计算机）。EricRoosendaal还在和其他人一起合作进行计算（包括再次验证以前的结果），如果你愿意加入这个研究项目的话，可以去访问上面给出的他的主页。