考拉兹猜想——像小孩游戏的规则，数学 80 年攻不下

大家好，我是 Senko。本文将解读被说成“数学还没准备好去应付的问题”的——考拉兹猜想。

先说规则。请随便挑一个正整数。偶数就除以 2，奇数就乘 3 再加 1。对得到的数重复同样的操作。比如 6，就是 6→3→10→5→16→8→4→2→1；7 则是 7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1。两个都落到了 1。猜想是这样的：“不管从哪个数出发，都会走到 1”。完了，规则说明到此为止。而这个玩儿一样的问题，数学 80 多年都没能证明。

27 展现的剧烈起落

这个猜想的瘆人劲儿，实际追一遍数就能体会。推荐的出发点是 27。

27 是个小数，可操作一开始，27→82→41→124→62→31→94→47→……，迟迟不肯往下走，反倒越涨越高，途中一路被抛上 9232 这个超过出发点 340 倍的高点。最后，它花了 111 步才降落到 1。

隔壁的 26 只要 10 步，28 要 18 步，唯独 27 走了一趟 111 步的长途。这种出发点只差一点点，轨道长度就变得无法预测的行为，正是考拉兹猜想核心的难处。数列的动作看不出规律，因此被比作冰雹在云里上下翻腾后才落地，还得了个“冰雹数列”的别名。

即便如此，每个数最后都会掉回 1。计算机验证已确认，直到约 2 的 68 次方（约 3×10^20）为止的所有数都能抵达 1。反例一个也没找到。

“当代数学还没准备好应付这个问题”

猜想的名字，来自据称在 1930 年代思考过这个问题的德国数学家洛塔尔·考拉兹。不过出处的记载含糊，战后在数学家之间靠口耳相传扩散，因此按经手数学家的名字，各国各时期还有“角谷问题”（源自日本的角谷静夫）、“乌拉姆猜想”等好几个别名。因为传得太广，据说还流传过“这是苏联放出的陷阱”这样的玩笑。

象征其危险性的，是流浪天才数学家保罗·埃尔德什的那句名言。

当代数学，还没准备好去应付这类问题。

埃尔德什以给有趣问题挂赏金闻名，而他给考拉兹猜想开出的是 500 美元。重点不在金额大小，而在于这句话作为“这是个一旦伸手就回不来的问题”的警告，在数学家之间被一代代讲下去。事实上，优秀的年轻人陷进这个问题里，一直被半开玩笑地当作“考拉兹病”来提防。

另一方面，1972 年，以“生命游戏”闻名的约翰·康威证明了：把考拉兹型规则一般化后的问题，在原理上可能是不可判定的。也就是说，这类“摆弄数字的简单规则”的家族里，确实存在逻辑之力原理上够不着的领域。至于考拉兹猜想本身是不是掉在那里面，尚不清楚。

这么简单的问题为什么证不出来

会觉得奇怪是自然的。规则才两行，到底难在哪儿？

最大的理由是，操作会把“进位”的结构破坏掉。除以 2 这个操作与二进制世界很合拍，乘 3 加 1 则与三进制世界合拍。可这两者交替纠缠起来，数的结构就在两个世界里被搅得无法预测。数论的传统工具依赖数的结构规律往前走，面对一边破坏结构一边前进的考拉兹数列，就没了立足点。

另一个理由是，反例有两种形态。猜想若为假，就该存在“无限发散下去的数列”或“不经过 1 的另一个循环”之一，而必须同时证明这两者都不存在。仅仅给出趋向 1 的“平均倾向”，是排除不掉那唯一一条例外的。

从统计上看，数列确实有下降的倾向。奇数乘 3 加 1 必定得到偶数，于是马上被 2 除，把操作抹平来算，平均每一步数是在缩小的。“平均必定下沉，却排除不掉例外”。这种概率上几乎已定罪、逻辑上却收不了网的格局，是本系列其他猜想也共有的、未解决问题的经典风景。

陶哲轩的“几乎全部”

在这个长期缺乏进展的问题上，2019 年，当代最顶尖的数学家之一陶哲轩刻下了一大步。

陶哲轩证明的东西，粗暴地概括就是“对几乎所有出发点而言，数列都会降到任意小的值”。这离“所有数都抵达 1”还差着，但它以迄今最强的形式表明了“几乎所有数几乎必定会沉下去”。在专家之间，这被评价为“接近所能期望的最好结果”。

有意思的是，陶哲轩在这项成果里部分引入了概率论的工具：把一个确定性规则的问题，当作概率问题来攻。正面破不开墙时就连擂台一起换掉——这种发想，我觉得是与未解决问题作战的范本。即便如此，陶哲轩本人仍不改谨慎，说“完全解决或许在射程之外”。埃尔德什那句警告的分量，至今仍活着。

从 1 倒着看，会长出一棵巨树

正着追是连续的上下翻腾，但也有把视角反转的看法：从 1 倒着往回走。

抵达 1 之前的数是 2，再之前是 4、8、16……倒着的操作有两种：“乘以 2”，以及只在条件吻合时才能用的“减 1 再除以 3”。从 16 既能分岔到 32 也能分岔到 5，所以倒着追溯时，就会长出一棵以 1 为根的巨树。考拉兹猜想可以换句话说成：这棵树“把所有正整数都含在某根枝上”。只要漏掉一个数，猜想就崩了。

画出这棵“考拉兹树”的图作为猜想的象征而闻名，枝条走向不规则、整体却又井然伸展的样子，被评为像血管、像闪电、像植物的枝。就“简单规则生出复杂形态”这一点而言，也可以当作分形的同类来欣赏。

顺带一提，不断刷新纪录的全数验证背后也有巧劲。某个出发点的数列只要有一次降到比出发点更小的值，验证就可以到此为止（因为比它小的数都已经验过了）。绝大多数数很快就会跌破出发点，光这一条省略就让计算量骤减。一个简单问题的世界纪录，背后同样是这类巧思与专用程序的工程总动员在撑着。

边玩边回答疑问

到了 1 之后会怎样

1 是奇数，乘 3 加 1 得到 4，于是 4→2→1 又转回来。也就是说，数列的终点准确地讲是“4→2→1 的永久循环”。严格表述猜想就是“所有正整数最终都会进入这个循环”。反过来说，所谓反例就是“进不了这个循环的数”，它要么是另一个循环，要么是无限上升。

换成负数，或者不是 3 倍而是 5 倍会怎样

推广到负整数，情形立刻变样：负的那一侧已发现多个与 1 无关的独立循环，反倒显得正的那侧的规矩才是例外。而若把规则改成“乘 5 加 1”，一般认为许多出发点的数列会发散出去。3 这个系数，似乎正处在下沉之力与上浮之力绝妙平衡的边界上。这种改规则的玩法用纸笔和计算器就能做，所以我推荐把考拉兹猜想当成“体验用”而非“观赏用”的未解决问题。

我好像在编程练习题里见过它

正是如此。考拉兹数列只用循环和条件分支就能写出来，是编程入门的经典课题。几行代码就能重现与未解决问题最前线相同的风景（比如 27 的剧烈起落）。不过一旦要冲击全数验证的世界纪录级别，话题就一下子变成加速技术的比拼——验证到 2 的 68 次方，也是靠 GPU 的专用程序才拿下的。写出来跑一跑看看只要 10 分钟，要挑战纪录则可能搭上一生。受众之广，我觉得也是这个问题被人喜爱的理由。