早上灌咖啡又刷到这个老梗，越想越好玩。
规则简单到爆，随便挑个正整数，偶数就除以2，奇数乘3加1，一直重复。比如6→3→10→5→16→8→4→2→1，最后全落到1。
有个叫Collatz的数学家1937年提出来的，快一百年了。好家伙计算机拿几百亿个数试过，统统回到1，但就是没法证明所有数都这样。
离谱吧，一个小学生都能照着算的规则，全世界数学家愣是证不出来。服了
我这种学语言的反正看个乐呵，总觉得这种简单又无解的东西特迷人。你们有人能讲讲它为啥这么难吗，还是说本来就是个坑。

几百亿个数试完愣是证不出，算力堆上去都白搭。我刚拿手机算了几个真全落回1，越算越上头哈哈。简单又无解的东西就是勾人，比一眼望到底的题耐玩多了

几百亿个数试了全回1，偏偏证不出，这剧情放小说里都算烂尾。你说的"简单又无解特迷人"我挺认同，像生活里照着规则走却说不清为啥的事，越琢磨越虚无。C’est la vie。

前阵子我也拿这题逗过家里小孩，算得贼起劲，一听说全世界都证不出来立马傻眼。这种越简单越没人能降住的反差才够味儿。我挺信它就是个坑，规则越朴素，里头的弯弯绕越不是靠堆数能填平的。管它证不证得出，先冲进去算两把再说！

这个验证数字说得太保守了，目前已知到 2^68（约 2.95×10^20）以内全都成立，远不止几百亿。难的从来不是算得够不够远，是奇步"×3+1"会把数推高、偶步"÷2"才把它压回来，两套节奏没法统一成一条递减规律，自然也没法归纳。

验证早就不止几百亿了，前两年已经推到2的68次方。它真正难的地方是找不到一个保证一直变小的量，每步乘3或除2，奇偶序列乱得像掷硬币，归纳法压根没处下手。

楼主说计算机试过几百亿个数，这个量级其实保守得有点离谱了。据我所知，3n+1 已经被数值验证到了大约 2 的 68 次方，也就是接近 3×10 的 20 次方，远不止几百亿，毕竟几百亿只是 10 的 10 次方出头。换句话说，在肉眼可见的算力范围内它确实没翻过车，但验证再多也永远填不满"所有正整数"这个无穷集合，有限个例永远支撑不起一个全称命题。

我倒觉得这题迷人的地方不在"难"，而在于它把"看起来显然"和"证不出来"之间的张力摆得特别干净。小学生能算、教授证不出，这种落差本身比答案更有意思。嗯

不过说"全世界都证不出"稍微有点绝对，更准确讲是既没人证出它恒真，也没人找到一个反例，开放了快九十年，两边都还空着。

把"证不出来"理解成"这是个坑"倒也有点意思，不过从数学上看，它更像是规则本身的结构逼出来的难，而不是谁故意设的陷阱。

先补一个数：你说的"几百亿个数试过"其实低估得挺多。这个猜想的暴力验证早就过了人类直觉的量级——目前已知的数值验证下限大约到了 10^20 这个量级（不同团队的细分边界略有出入，但都早已远超几百亿），也就是几亿亿级别的数统统落回了 1。所以"试不出反例"这件事，规模早就不在几百亿这个档位了。

至于为什么这么难，我觉得关键在它没有一个能"压制"全局的不变量。偶数除以2是往下拉，奇数乘3加1是往上推，两步操作方向相反，整个序列走起来像在两种力之间乱晃，没有一个单调的量（比如始终递减的函数）让你能拍着胸脯断言"它早晚会塌到1"。经典证明里那种"构造一个递减序列，于是必然终止"的套路，在这里基本使不上劲。

还有个更劝退的角度。Conway 在七十年代就证明过，把 Collatz 的玩法推广成一类类似的模迭代之后，这类问题里存在图灵不可判定的实例——也就是广义版本里确实有的情形是"永远算不出答案"的。这虽不等于原问题不可判定，但至少说明这种"规则极简、行为却混沌"的问题，天然就容易踩到计算理论的边界。

所以我觉得它迷人恰恰在反面：难度不是来自规则复杂，而是来自规则跑起来之后的不可预测。这比一个精心设计的"坑"要耐人寻味得多。你们搞语言的要是拿它当隐喻，倒是比我们这些较真数据的人更能品出点滋味来。

帖子里说计算机拿几百亿个数试过，这个数字其实保守得有点离谱了。我前几年闲着翻资料顺手记过一笔：葡萄牙数学家 Tomás Oliveira e Silva 在2008年前后就把验证范围推到了约 5×10^18，后来又有团队一路算到 2^68（接近 3×10^20）以内，全部确认归于1。几百亿只是 10^10 量级，跟现在的实际尺度差了快十个数量级，属于很早以前的旧数据。

至于"为啥这么难"，楼主问得挺到点子上。我的粗浅理解是，这规则表面简单，但每一步往上乘3加1、往下除2，两股力道搅在一起，整体既不单调增也不单调减，常规归纳法套不进去。说它是"坑"倒不至于，题本身是干净的，只是现成的工具暂时够不到那个证明。

另外1937年那个年份也得留个心眼：严格说不是 Collatz"正式提出并发表"的时间，他大概那阵子在哥廷根跟人聊起过这想法，没写成论文，是后来别人整理传播开的。所以"提出者加年份"这套说法，史实上没那么利落。

这种流传了快百年的老梗，年份和出处最容易以讹传讹，也正常。

说真的，我这种看见公式就头疼的，反而觉得它迷人得很。几百亿个数全认了怂，就差一句定理压死人，这不是明摆着挖坑吗哈哈

补充一个数据：验证范围早不止几百亿了，现在起码到 2^68 这个量级，一样没找到反例。

早上灌咖啡刷到这个我也挺有共鸣的，这种"规则一眼看懂、证明却遥遥无期"的反差确实特别迷人。

关于它为啥难，我个人的感觉是——难的不是算，而是"所有数"这三个字。单个数字你闷头算总能跑到1，但数学要的是一张把所有情况都兜住的网。嗯嗯这规则看着简单，可它既不是纯加法也不是纯乘法，奇偶一交替，每个数的走向就没法用一套整齐的公式套出来。乘3会让数变大、除以2会让数变小，两种力量一直拉扯，目前根本没有办法保证"任何一个数都不会永远涨下去、也不会卡进某个回不到1的循环"。

不过你说的"本来就是个坑"也挺有意思，确实有人怀疑它是不是属于"不可判定"那一类问题——就是可能根本没法在现有框架里被证明或证伪。会好的这样想想反而更带感了。

你学语言的反而比我们这些喜欢较真的人更能享受这种纯粹的好奇，挺好的。