【数学】3x+1问题(2)

作者:异调

三、一些概念,一些纪录

虽然证不出猜想,但是数学家们还是得到了许多很可能很有用的结论。 让我们先来定义几个概念,然后再来介绍这些结论。 从一个自然数开始,用上面这个变换,我们可以计算出一串自然数的 序列。为了形象起见,我们把这串数列叫做以最初用来开始计算的那 个自然数命名的“航班”。比如说,第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班航班列出一个相关数据表来:

下面要说说几个记录。在上面我们已经说过,目前3x+1问题已经被检验到100*250=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还在和其他人一起 合作进行计算(包括再次验证以前的结果),如果你愿意加入这个研 究项目的话,可以去访问上面给出的他的主页。

大学生数学竞赛题汇编
大学生数学竞赛题
高中数学联合竞赛试题
国际象棋中的趣题妙解
数学家俱乐部
数学趣题汇编
牛顿:在海边寻找贝壳的人
凯尔文:是上帝创造了生命,并且掌管一切
陆地动物能变成鲸吗
数学界的奇人妙事
趣味逻辑学问题

Conway: 游戏人生
有关孪生素数的一个有趣猜想
素数之恋-伯恩哈德·黎曼
等分布理论简介
数学家波利亚
物理学之神奇的数
鸟和青蛙
超级圆周率π运算器
数学难题汇编
3x+1问题(1)

此条目发表在数学分类目录,贴了, , , 标签。将固定链接加入收藏夹。