最出名也最难的考拉兹猜想

如果你对标题中的“考拉兹猜想”感到陌生，我说说它的其他名字，你是不是能想起来：奇偶归一猜想、3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想和叙拉古猜想。

如果你还没有想起来，我就再复述一下这个猜想的内容，看看你是不是能反应过来。这个猜想是这样说的，任取一个自然数，如果它是奇数，那么就把它乘以3再加1；如果是偶数，就把它除以2。把得到的结果再重复上述过程，这个过程也叫作“考拉兹变换”，最后，无论你取什么样的自然数，重复上述过程后，你最后会进入一个4，2，1的循环。该猜想又名为“奇偶归一猜想”或“3n+1”猜想。

怎么样，我敢打赌你看到过这个猜想，也曾经在纸上尝试写几个自然数去验证它，相信很多人都有过这样的经历。在小学时我就看到过这个猜想了，没想到几十年过去了，这个猜想还是没有解决。

为了给之前不了解这个猜想的人来点感性认识，我们还是简单验证一个数字，比如6。6是偶数，除以2，得3；3是奇数，那乘以3加1，得10。此后的序列是5，16，8，4，2，1。到1之后，若继续算，那么又会得到4，然后进入4，2，1这样的循环。“考拉兹猜想”认为，所有自然数经过这样的迭代转换，最后都会进入4，2，1的循环。你看这个问题是不是够简单了，小学4年级学生绝对可以理解的。

这个猜想最早是在20世纪30年代，由当时还是大学生的德国数学家考拉兹提出的。20世纪60年代，日本人角谷静夫也研究过这个猜想，并让这个猜想流传到中国，所以在中国，这个猜想曾经被称为“角谷猜想”。

这个猜想看上去如此简单，但为什么又这么难？我请你再做一个试验，请你拿一个计算器，对27这个数字进行验证。这个数字看上去很小，但我打赌你尝试10分钟后，就放弃了。因为在你进行了五六十轮计算之后，验证还没有结束的迹象。接近80步的时候，你会得到一个惊人的数字9232，你看从27到九千多是不是很吓人。但之后，只要你坚持到第110步，整个数列如预期的一样，回到了1。而验证数字26只要10步，验证数字28只要18步，所以这里面完全看不出明显的规律来。

数字27的完整验证步骤如下，其中最大的数是9232，共有111个步骤：

{27，82，41，124，62，31，94，47，142，71，214，107，322，161，484，242，121，364，182，91，274，137，412，206，103，310，155，466，233，700，350，175，526，263，790，395，1186，593，1780，890，445，1336，668，334，167，502，251，754，377，1132，566，283，850，425，1276，638，319，958，479，1438，719，2158，1079，3238，1619，4858，2429，7288，3644，1822，911，2734，1367，4102，2051，6154，3077，9232，4616，2308，1154，577，1732，866，433，1300，650，325，976，488，244，122，61，184，92，46，23，70，35，106，53，160，80，40，20，10，5，16，8，4，2，1}

如果要进一步理解这个猜想，我还是用一个常用的比喻来说明。我们可以把整个考拉兹猜想的运算过程想象成一个飞机的航线。开始的数字，是飞机的起始高度。中间每一步的运算都可以想象成飞行高度的变化。整个航线会结束在1这个最低点，而航线的长度就是整个考拉兹运算的步骤数。比如27号航线，起始高度是27，航线最高点到了9232，航线总长111，最终安全降落在1的高度。

稍微思考一下，你就会发现很多航线是共享的，比如“27号航线”，最高到了9232。其实也可以认为从这个点开始，它就按“9232号航线”的路线飞行了。你也可以发现9232号航线要比27号航线短许多，尽管9232号航线起飞高度要比27号高很多。

现在的计算结果表明航线号在1万以内的，最长的是6171号，总长是261。1亿以内的，航线最长的是63,728,127，共有949个步骤。目前已经有人用计算机验证到5×1018，在这个范围内也没有发现反例。但与许多问题一样，验证再多也不能对证明这个问题产生任何帮助。

因为所有的航线最终都汇聚到一起，所以有点百川入海的感觉，如果倒过来看，又很像一棵树，根部是1，然后上面是2，4，产生很多分叉。有人把整棵树画了出来，请你感受一下，是不是很有神秘感？

如果有人能证明这棵树可以覆盖所有自然数，就等于是证明了考拉兹猜想。2011年考拉兹的一个学生声称证明了考拉兹猜想，但事后发现他的证明里有一个小的缺陷，是因为他在证明中利用到的一棵树，没有证明覆盖到所有自然数。到现在过了8年，这个缺陷还是没有被补上，所以考拉兹猜想还是猜想。

目前对考拉兹猜想最好的证明成果是在2003年由2位研究者创造的，他们证明了从1到第n个自然数里，符合考拉兹猜想的自然数数量远大于n0.84。比如，n取10000，就是说10000以内符合考拉兹猜想的自然数数量远大于100000.84≈2291。你可能会说这个结论很弱嘛，而且表达有点含糊，什么叫“远大于”呢。其实这恰恰说明了这个猜想很难，而数学家也很严谨。虽然说远大于n0.84，很可能换成大于n0.9甚至大于n0.9999，但是证明达不到这一点，所以数学家就不会这么说。

作为对比，如果你用中文搜索“考拉兹猜想”或者“角谷猜想”，能发现好多人声称证明了这个猜想，还有极少数人声称推翻了这个猜想。有些证明甚至短得不到一屏，但这些证明的漏洞都太明显。相比之下，英文网页里就有很多考拉兹猜想的科普文章，就这一点我觉得中国人的数学科普工作还是任重道远。

谈到英文网页，我找到了一篇由非常杰出的澳籍华裔数学家陶哲轩在2011年写的一篇博客，在博客中，他谈了对考拉兹猜想的一些研究心得和感想。

我简单介绍一下这篇博客的内容，虽然是博客里的文章，但内容还是非常艰深的，我也只能把其中的主旨和要点告诉大家，带领大家看看数学家的思维方式。

首先，陶哲轩说考拉兹猜想有点像另一位数学家说到过的“数学疾病”。为什么是疾病？就是因为这个猜想太出名，而题目本身的概念太简单，导致很多人过度迷恋它，纠结于这个猜想，因而浪费了大好时光。

其实数学里很多难题的解决并不能纠结于问题本身，而经常是在其他领域或其他问题取得重大突破后，把这个突破运用到原来的问题中，最后得以解决问题的。最典型的例子就是费马大定理的证明，有人发现费马大定理是“谷山-志村猜想”的一个推论，如果证明了“谷山-志村猜想”，就等于证明了费马大定理。

安德鲁·怀尔斯在了解到这一点之后，觉得他有一些思路可以攻克“谷山-志村猜想”，所以他就开始朝这个方向进攻，最后，通过谷山 -志村猜想推导出费马大定理。这件事情告诉我们：对一个特定数学难题太过迷恋或纠结是不好的。好的办法是广泛地学习和了解更多有关数学领域的知识，然后你才能发现解决一个问题的最好办法。

其次，陶哲轩也认为考拉兹猜想不是数学家目前应该主攻的问题，因为理论工具还没准备好。他认为一个成熟的数学家应该主要考虑那些刚好超过数学工具边缘的问题。这虽然很好理解，但是对数学家的要求非常高。你需要知道有哪些数学工具可用，也需要了解解决一个问题可能会用到哪些工具，还要对它的难度有很好的估计。不过通过这句话，我想奉劝各位，不要痴迷于解决考拉兹猜想了，这不是业余爱好者可以解决的问题。

接下来，陶哲轩对考拉兹猜想做了一些很有意思的启发式讨论。所谓“启发式”，是说这种讨论绝不是严格的证明，只是对问题的一种估计、联想和类比。

首先，他说了一个众所周知的联想。原先在考拉兹变换过程中，遇到奇数乘以3加1，而奇数乘以3加1必定为偶数，所以我们可以略加修改，改成：遇到奇数我们就乘以3加1再除以2，因为必定可以整除嘛。除完结果是奇数还是偶数就不一定了。遇到偶数仍旧除以2，结果也是奇偶不定。我们可以把这种变换过程叫作“压缩考拉兹变换”。

这时可以观察到，一个奇数经过这种压缩考拉兹变换后大概是变成原来的1.5倍，偶数则变为一半。如果任何一整数在压缩过的考拉兹变换过程中，所经过的奇数和偶数数量都差不多各占一半的话，那么也就是有一半的机会增加为1.5倍，另有一半机会变为原先数值的一半，所以总体上是变小的，这是一个有利于证明考拉兹猜想的论据。但请注意，这只是一个启发式论据，不是严格证明。

而且更重要的是，即使证明整数在变换过程中经历的奇偶数概率各占一半，也完全不能证明考拉兹猜想。因为这既不能否认有“4-2-1”以外的循环，也不能否认有某个数会发散。证明了一个基于概率的性质，你总不能否定有一两个特例会偏离这种概率性质吧？网上有的“证明”就是用这种概率分布来说明问题的，我很想说这根本不起作用。可能有用的是证明一种“极限”性质，比如你证明任何一个数，经过足够多的压缩考拉兹变换后，经历的奇数和偶数的数量趋于相等，而且奇数不会比偶数多于一定值，这大概是有用的。但这个命题跟前面概率性质的命题难度相比，简直是天差地别。

回到陶哲轩的文章。其次，他也说，以上的启发式推测只是提示人们大多数自然数的运行轨道是缩小的，但是它不能排除有其他循环轨道或者很特殊的发散数。接下来他进一步考察了一下有其他循环轨道的可能。

他首先提出了一个“弱考拉兹猜想”的命题：假设某个正整数在经过考拉兹变换后，又能回到自身，产生循环，那么这个正整数只能是1，2，4三者之一。这个命题就是说只有“4-2-1”这一种循环。为什么叫它“弱考拉兹猜想”呢？因为证明它，并不能证明考拉兹猜想，因为还有一种产生发散的可能。但是证明考拉兹猜想，就等于证明了它，所以显得比较“弱”。这也是数学里常用的一种思考方法，当原命题太难的时候，我们适当放宽条件，得出一个弱一点的结论。如果能证明的话，那至少离目标近了点。

那现在有了这个弱命题有什么用呢？很有用。有两个研究者发现这个弱考拉兹猜想等价于另一个命题：

不存在某个自然数k≥1，和以下数列：

使得2ak-1-3k是一个整数，且能整除：3k-12a1+3k-22a2+…+2ak。也就是不存在正整数k和n，使得以下等式成立：

这个等价命题看上去复杂，但数学家认为很好处理。原来考拉兹猜想的一大难点在于它是个迭代和动态的过程，甚至动态当中有“混沌”的意味，用现有工具不好处理。但是，现在这个等价命题则是一个关于2和3的幂次相乘和相加之后，有没有一种特定形式的因子的命题。这是一个相对静态的命题，而且也有一些数学工具可以处理。

当然，陶哲轩也说，他没能证明这个弱考拉兹猜想的等价命题，但是他对这个等价命题分析了一下。他认为如果这个等价命题不成立，也就是弱考拉兹猜想有其他循环的反例，那么这个循环的长度至少是105000。我们已经对5×1018以内的自然数都验证过考拉兹猜想了，所以要有反例的话，请你想象一下105000个19位以上的自然数的序列，构成一个考拉兹循环。如果这个循环存在的话，简直要颠覆我对数学美学的信念，但现在就是不能证明它不存在。

最后，陶哲轩又探讨了弱考拉兹猜想如果成立的话，能产生的一些推论。你可能要问，弱考拉兹猜想都没有证明，考虑它的推论干吗？这就是数学家具有的一个很厉害的思路：把从弱考拉兹猜想可以推出的结论与已知结论相比，看它们到底差多远。

如果它比已知结论要强很多的话，那就提示我们：证明弱考拉兹猜想所需的知识要比我们已有的知识难很多。比如，从考拉兹猜想可以推出费马大定理的话，那还好，毕竟人类已经证明了费马大定里。但如果从考拉兹猜想能推出黎曼假设，那就不太好了，因为证明它至少跟证明黎曼假设是一个难度了。

陶哲轩从弱考拉兹猜想中得出了两个推论，如下：

推论1：如果“弱考拉兹猜想成立”，则对任何自然数a和k，以及2a>3k，有2a-3k>>k。

其中“>>”是“远大于”的意思。可以稍微验证一下，比如24>32，则以上命题认为24-32=16-9=7>>2，似乎是挺有道理的。

推论2：如果“弱考拉兹猜想成立”，则对任何自然数a和k，以及2a>3k，有2a-3k>>(1+ϵ)k，

其中ϵ是某个正数。这个推论是之前的加强版，(1+ϵ)k通常比k要大多了。

陶哲轩通过分析以上弱考拉兹猜想的推论得到：任何试图证明考拉兹猜想的途径，要么是用到“超越数理论”；要么是用一种全新的技巧，能够完美地对2的幂次和3的幂次进行隔离。这里的“超越数理论”指的是有关“超越数”的理论，这句话的具体意思我说不清，但我知道我是肯定不会花时间去尝试解决考拉兹猜想的。任何网上出现那种用初等数学推导出来的证明，都必定是错误的。

现在讲讲这个猜想的扩展。首先考虑一下，如果把负数也引入进来会如何？因为负数也是可以分奇偶的嘛。人们发现引入负数之后，考拉兹运算又多了3种循环：

-1→-2→-1

-5→-14→-7→-20→-10→-5

-17→-50→-25→-74→-37→-110→-55→-164→

-82→-41→-122→-61→-182→-91→-272→-136→

-68→-34→-17

最后一种很诡异，因为长度达到了18。当然，人们还是没有证明以上是否就是全部循环。

另一种扩展是被称为自然数范围内一般化的考拉兹猜想。原先的考拉兹猜想是分奇数和偶数两种情况。那可以很自然地推广下去：

对任意素数，根据余数分别定义一个线性变换。比如，取素数3，可以定义变换为：

除以3余1的，就乘3加1；除以3余2的，乘3加2；整除3的，再乘1/3。当然具体变换可以随意定义，只要是线性的。这样得到的变换称为一般化的“考拉兹猜想”。

这个问题的一个相关结论是1972年由约翰·康威（“三人分蛋糕”问题中提到过他）证明的。康威证明了一般化的考拉兹猜想是“不可决定的”，英文叫“undecidable”。“不可决定的”，简单来说就是：不可能有这样一个电脑程序，输入任何一个整数，这个程序可以在有限的时间里告诉你这个整数经过一般化的考拉兹变换是否能进入循环状态。康威的证明否定了这种程序的存在。

这个问题可以类比判定一个数是不是素数的问题。判定一个数是不是素数，就是“可以决定”的问题。尽管这个程序可能会运行很长时间，从几天到几年（比如判定梅森数是否为素数），但这个程序肯定能在有限时间内告诉我这个数是不是素数，但针对“一般化的考拉兹问题”就没有这样的程序。

这就提示我们，一般化的考拉兹猜想的收敛性是不可能有证明的，除非是证明发散。如果能证明收敛到一些循环，等价于可以有某个程序，总是可以停机的，这就跟康威的结论矛盾了。但幸而对特定取值的考拉兹运算，比如原版的考拉兹命题，陶哲轩认为，总体上的趋势是在变小的，所以看上去并不是不可决定的，所以他认为原版命题还是有证明的希望的，只是时机未到。