3n1猜想学名科拉兹猜想也叫角谷猜想、冰雹序列。规则一句话就能说完给你一个正整数 n如果它是偶数就除以 2如果它是奇数就乘以 3 再加 1。反复执行这个过程不管从哪个数开始最后都会掉进 4 → 2 → 1 这个循环里。这个“不管从哪个数开始”就是至今没人能证明的猜想但计算机已经替我们验证了极其庞大的范围目前没找到反例。我这次用 C 把这个算法完整落地顺便把“看似简单其实一踩一个准”的问题都梳理清楚整数溢出、循环判断、缓存加速、区间统计以及最终一份能直接交作业、能拿去跑实验的源码。适合刚学 C、想用一个小项目练手的人也适合想理解“算法思路 工程实现”怎么结合的人。读懂这一篇你不仅会写 3n1还会明白为什么很多看似简单的递归算法落地时总有一堆意想不到的坑。1. 3n1 猜想到底是什么1.1 一个简单到反常的规则先拿一个具体数字走一遍。假如从 6 开始6 是偶数除以 2 → 33 是奇数乘以 3 再加 1 → 1010 是偶数除以 2 → 55 是奇数乘以 3 再加 1 → 1616 是偶数除以 2 → 88 是偶数除以 2 → 44 是偶数除以 2 → 22 是偶数除以 2 → 1整个过程是 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1一共 8 步到达 1。这里用“步数”指从起始数变换到 1 所需要的操作次数。它被叫作“冰雹序列”是因为这个数列很不安分上升、下降、再上升、再下降像冰雹在高空云层里反复翻腾但最终一定会落到地面上。比如从 27 开始序列长度会拉到 111 步中间最大值甚至可以冲到 9232最后照样跌回 1。换个角度看如果我们定义一个函数 f(n)那么整个 3n1 就是在反复套用 fn 为偶数时f(n) n / 2n 为奇数时f(n) 3n 1这几乎是最简单的分段函数了没有任何复杂的数学操作。但正是这种简单让无数人着迷一个小学三年级都能看懂的规则却长期无法被严格证明“所有正整数都会走到 1”。1.2 用 C 实现它的真正价值有人会问这么简单的算法直接写几行 while 循环不就行了值得专门用一篇博文来讲吗其实这里面的门道不少。纯数学爱好者喜欢用纸笔演算但程序员的视角完全不同我们关心的不只是“结果是不是 1”还包括程序能不能在合理时间内跑完、会不会因为数字太大而溢出、能不能通过缓存把重复计算砍掉、以及如何把单个数验证扩展成区间统计。3n1 看起来只有一个循环却能把 C 里几个重要概念全部串起来整数类型的溢出风险循环终止条件的严谨性递归、迭代、记忆化三种实现思路性能优化缓存、位运算、批量处理输入输出与错误处理这也是 C 特别适合实现 3n1 的原因。Python 之类的高级语言对大整数宽容很多但你会失去对内存和整数类型的掌控感。C 的强类型、固定位宽、甚至__int128扩展能让你真实感受到“数值范围”在算法实现里有多重要。2. 基础实现先把循环跑起来2.1 最朴素的迭代代码第一版代码不要过度设计先把规则翻译成程序。核心逻辑就一句话只要 n 不是 1就根据奇偶性做一次变换。#include iostream using namespace std; // 返回从 n 到达 1 需要多少步 long long collatz_steps(long long n) { long long steps 0; while (n ! 1) { if (n % 2 0) { n n / 2; } else { n 3 * n 1; } steps; } return steps; } int main() { long long n; cout 请输入一个正整数: ; cin n; if (n 0) { cout 输入必须是正整数 endl; return 1; } cout 从 n 到达 1 共需要 collatz_steps(n) 步 endl; return 0; }这段代码所有 C 学习者都能一眼看懂while控制循环if-else判断奇偶steps累计步数最后返回结果。在 main 里先做输入校验防止用户输入 0 或负数。运行示例请输入一个正整数: 6 从 6 到达 1 共需要 8 步这就是 3n1 的骨架。你甚至可以把collatz_steps改成递归版本逻辑完全等价long long collatz_steps_recursive(long long n) { if (n 1) { return 0; } if (n % 2 0) { return 1 collatz_steps_recursive(n / 2); } return 1 collatz_steps_recursive(3 * n 1); }递归版本更贴近数学定义但深度可能非常大。某些数字的序列路径会很长虽然大多数情况下递归栈够用但在极端场景下迭代版本更稳也更容易和后续的“记忆化”结合。2.2 输入输出与边界处理基础版代码有一个值得注意的设计先判断n 0直接拒绝非法输入。这不是多此一举。3n1 猜想的研究对象是正整数输入 0 时循环条件n ! 1永远成立而且 0 是偶数会一直停在 0输入负数时也一样程序会变成死循环因为负数经过几次变换也回不到 1。另外你可能会在网上的旧代码里看到有人用int存 n然后从 27 开始测试结果程序跑了很长时间甚至出现了奇怪的数值。原因不在算法而在整数溢出。看一下这个过程起始 27 的序列中间会出现 9232看上去int也装得下但我们能保证所有起始值都不会超过 21 亿吗不能。有些起始值在变换过程中会先飙升到非常大的中间值比如从 71 开始序列峰值约 4616但某些更大起始值的序列峰值会突破 32 位范围。所以从第一版就用long long是明智的。如果你非要用int跑实验推荐只在起始值较小的范围内测试比如 1 到 1000。一旦把区间上限调大int随时可能给你表演“负数和溢出”。2.3 一个明显的坑int 溢出举个让人印象深刻的例子有些资料说“从 27 开始的序列最大值为 9232”这让很多人误以为int足够。但如果你用程序搜索 1 到 100000 范围内的所有起始值会发现不少序列中间产生的数值远超int上限。这个坑的根源在于3n1 的变换是“放大”和“缩小”在反复拉锯奇数项会把数放大三倍多而偶数项只能除以 2。一旦连续出现几个奇数数值就会快速膨胀。出现溢出时会发生什么C 里有符号整数溢出是未定义行为实际中常见的表现是负数、错误的结果、甚至死循环。比如某个数在溢出后变成负数程序再用n % 2 0判断时可能永远不满足收敛条件。这也是我坚持第一阶段就上long long的原因。C 标准只保证long long至少 64 位而 64 位能覆盖绝大多数教学和验证场景。3. 大数版实现避开整数溢出3.1 升级到 unsigned long long如果你只想做“整数验证”long long已经够了但有些追求严谨的开发者会把类型换成unsigned long long。因为 3n1 处理的全是正整数用无符号类型在语义上更贴切也能省下符号位让正数范围比long long大一倍。#include iostream using namespace std; unsigned long long collatz_steps_ull(unsigned long long n) { unsigned long long steps 0; while (n ! 1) { if (n % 2 0) { n / 2; } else { n 3 * n 1; } steps; } return steps; }注意n 3 * n 1这里3 * n和n 1的运算都在unsigned long long范围内进行只要起始值不是特别离谱就不会出问题。但问题也来了如果用户输入一个很大的 64 位整数比如接近unsigned long long上限的某个数那么3 * n 1在数学上可能超过 64 位无符号整数的表示范围。这时候我们需要更宽的整数类型。3.2 进阶版__int128GCC 和 Clang 都支持__int128这个扩展类型它不是 C 标准的一部分但在 Linux 环境下非常常用。它允许你使用 128 位整数能让 3n1 的验证范围大大扩展。#include iostream using namespace std; using i128 __int128_t; // 打印 __int128因为 iostream 不支持直接输出 void print_i128(i128 x) { if (x 0) { cout 0; return; } if (x 0) { cout -; x -x; } char buf[64]; int idx 63; buf[idx--] \0; while (x 0) { buf[idx--] (x % 10) 0; x / 10; } cout (buf idx 1); } i128 collatz_steps_i128(i128 n) { i128 steps 0; while (n ! 1) { if (n % 2 0) { n / 2; } else { n 3 * n 1; } steps; } return steps; } int main() { long long input; cout 请输入一个正整数: ; cin input; if (input 0) { cout 输入必须是正整数 endl; return 1; } i128 steps collatz_steps_i128(input); cout 从 input 到达 1 共需要 ; print_i128(steps); cout 步 endl; return 0; }用__int128之后能处理的起始值上限就高了很多中间过程也很难溢出。不过要注意cin和cout无法直接读写__int128所以代码里加了print_i128作为辅助函数。这种细节就是实际工程中会遇到的真实麻烦算法本身简单工具链的兼容性反而成了切入难点。3.3 为什么奇偶判断这么关键写 3n1 时最核心的底层操作就是“判断奇偶”。判断对了后续缩放才有意义判断错了整个序列就全乱套了。很多新手喜欢写n % 2 1判断奇数。这种写法在 n 为正数时没问题但如果你用long long且某个中间值溢出成了负数负数取模在 C 里结果可能是负数比如-3 % 2 -1那么n % 2 1就恒为假程序会误判所有负奇数为“偶数”接着逻辑全乱。更稳妥的习惯是用位运算if (n 1) { // n 是奇数 } else { // n 是偶数 }n 1只检查二进制最低位最低位是 1就是奇数是 0就是偶数。这个判断在正负数上都稳定执行速度也比取模略快。在大量区间搜索时位运算的好处会被放大。同样的道理除以 2 也可以用右移操作n 1它只做单纯的位搬移不涉及符号位的复杂判断。不过对于正数n / 2和n 1结果完全一样前者语义更清楚后者性能略好。二选一取决于你的代码风格。4. 性能优化别让程序空转4.1 记忆化搜索重复计算砍掉一大半基础版代码只有一个循环但如果你要验证 1 到 100 万的所有数就会发现程序其实做了大量重复劳动。比如从 10 开始是 10 → 5 → 16 → 8 → 4 → 2 → 1而从 5 开始则是 5 → 16 → 8 → 4 → 2 → 1。后面的路径完全一样但两段循环各自独立计算了一遍。解决办法是记忆化。把每个已经算好的数的“到达 1 所需步数”存起来下次遇到这个数时直接查表。#include iostream #include unordered_map using namespace std; unordered_maplong long, long long memo; long long collatz_steps_memo(long long n) { if (n 1) { return 0; } auto it memo.find(n); if (it ! memo.end()) { return it-second; } long long steps; if (n % 2 0) { steps 1 collatz_steps_memo(n / 2); } else { steps 1 collatz_steps_memo(3 * n 1); } memo[n] steps; return steps; }这里用递归 哈希表。递归的好处是自然表达“先算出子问题再加一步”哈希表负责缓存结果。如果你做区间搜索比如统计 1 到 1000000 之间谁的步数最多记忆化的优势非常惊人。很多路径会汇聚到同一条主干上查表命中率很高。实测下来百万级区间搜索用记忆化可以比朴素循环快好几倍数字范围越大优势越明显。4.2 区间统计与批量处理单个数的验证只是基础实际项目里更常见的需求是“找出 1 到 N 之间哪个数的序列最长、最长步数是多少”。这类问题非常适合用记忆化批量处理。#include iostream #include unordered_map using namespace std; unordered_maplong long, long long memo; long long get_steps(long long n) { if (n 1) { return 0; } auto it memo.find(n); if (it ! memo.end()) { return it-second; } long long next (n % 2 0) ? (n / 2) : (3 * n 1); memo[n] 1 get_steps(next); return memo[n]; } int main() { long long limit; cout 请输入搜索上限 N: ; cin limit; long long best_num 0; long long best_steps 0; for (long long i 1; i limit; i) { long long s get_steps(i); if (s best_steps) { best_steps s; best_num i; } } cout 在 1 到 limit 范围内 endl; cout 序列最长的数是 best_num endl; cout 最长步数: best_steps endl; return 0; }运行示例请输入搜索上限 N: 100 在 1 到 100 范围内 序列最长的数是 97 最长步数: 118这里有个工程细节值得关注memo会随着递归不断增长。区间搜索时如果 N 很大哈希表占用的内存也会变大。在实际使用中可以限制缓存大小或者改用数组缓存当 n 小于某个阈值时直接查数组超过阈值才走哈希表这样可以兼顾速度和内存。4.3 位运算优化到底能快多少很多人把位运算当成“炫技”但在这里它确实有实打实的作用。比如n 1代替n % 2 0判断奇偶n 1代替n / 2这两个替换在逻辑上完全等价但位运算避免了取模运算中的除法指令在大规模循环时能减少 CPU 开销。还有一个更高级的优化如果 n 是偶数可以一次性连续除以 2直到 n 变成奇数。比如 n 48二进制是110000除以 2 一次变成 24再除变成 12再除变成 6再除变成 3。与其每除一次判断一次不如直接数一下最低位后面有几个 0然后一步到位。while (n ! 1) { // 连续消除因子 2 while ((n 1) 0) { n 1; steps; } if (n 1) { break; } n 3 * n 1; steps; }这种“步进式跳过”其实就是循环展开思路数学本质没变但循环次数会减少。尤其当 n 的二进制末尾有大量 0 时一次就能抵消多轮偶数变换。实测中一个显著好处是减少递归深度让程序更不容易爆栈。5. 完整源码与用法解析5.1 一份可直接编译运行的完整源码前面几节把关键模块拆开讲了现在把它们整合成一份功能相对完整、可直接g编译运行的源码。支持两种模式单数验证和区间搜索。#include iostream #include unordered_map #include vector #include string using namespace std; using i128 __int128_t; unordered_mapi128, i128 memo; void print_i128(i128 x) { if (x 0) { cout 0; return; } if (x 0) { cout -; x -x; } char buf[64]; int idx 63; buf[idx--] \0; while (x 0) { buf[idx--] (x % 10) 0; x / 10; } cout (buf idx 1); } i128 get_steps(i128 n) { if (n 1) { return 0; } auto it memo.find(n); if (it ! memo.end()) { return it-second; } i128 next; if (n 1) { next 3 * n 1; } else { next n 1; } i128 steps 1 get_steps(next); memo[n] steps; return steps; } void run_single(long long start) { i128 n start; i128 steps get_steps(n); cout 单数验证模式 endl; cout 起始数: start endl; cout 到达 1 所需步数: ; print_i128(steps); cout endl; // 顺便输出序列路径但只展示前 20 项和末 5 项避免刷屏 vectori128 prefix; i128 cur start; for (int i 0; i 20 cur ! 1; i) { prefix.push_back(cur); if (cur 1) { cur 3 * cur 1; } else { cur 1; } } cout 序列头部: ; for (i128 v : prefix) { print_i128(v); cout - ; } cout ...; cout endl; } void run_range(long long limit) { i128 best_num 0; i128 best_steps 0; for (long long i 1; i limit; i) { i128 s get_steps(i); if (s best_steps) { best_steps s; best_num i; } } cout 区间搜索模式 endl; cout 搜索范围: 1 到 limit endl; cout 最长序列起始数: ; print_i128(best_num); cout endl; cout 最长步数: ; print_i128(best_steps); cout endl; } int main() { cout 3n1 猜想验证程序 endl; cout 1. 验证单个数 endl; cout 2. 搜索区间内最长序列 endl; cout 请选择模式: ; int mode; cin mode; if (mode 1) { long long start; cout 请输入起始数: ; cin start; if (start 0) { cout 起始数必须是正整数 endl; return 1; } run_single(start); } else if (mode 2) { long long limit; cout 请输入搜索上限 N: ; cin limit; if (limit 0) { cout N 必须是正整数 endl; return 1; } run_range(limit); } else { cout 无效选择 endl; return 1; } return 0; }这段代码把__int128、记忆化、位运算、区间搜索都整合在一起。本身就是一份“中等复杂度”的 C 练手项目非常适合用来练习头文件组织函数拆分类型别名using i128 __int128_t哈希表缓存设计程序菜单交互5.2 编译与使用说明在 Linux 或 macOS 终端下编译g -O2 -stdc17 collatz.cpp -o collatz-O2让编译器做常见优化包括循环优化和函数内联对越大的搜索区间收益越明显。-stdc17明确指定 C17 标准虽然这段代码在 C11 下也能编译但写上标准版本是好的工程习惯。-o collatz指定输出文件名。运行./collatz然后按菜单提示选择模式即可。如果你想在 Windows 下用 Visual Studio 编译__int128并不原生支持。一种办法是把i128换成long long这样在 Windows 下也能跑只是能处理的数值范围变小。另一种是使用 MSVC 的 128 位整数扩展但跨平台性不佳。所以如果遇到“为什么我的电脑编译不过”的问题大概率是__int128的编译器兼容性问题换成long long就行。5.3 用文件改造扩展成实验工具如果你想拿这个项目做更深入的实验可以考虑加一个“输出序列到文本文件”的功能。比如把 27 的完整序列写进sequence.txt然后用外部绘图工具画一条折线图。关键是别把所有输出都堆在终端因为序列一长终端就卡。写文件更合适。#include fstream void dump_sequence(long long start, const string filename) { ofstream fout(filename); long long n start; while (n ! 1) { fout n \n; if (n % 2 0) { n / 2; } else { n 3 * n 1; } } fout 1 \n; fout.close(); }有了这个输出你可以把 3n1 序列丢进任何数据分析工具里观察规律验证“上升比”“最大值”“偶奇交替模式”。这也是把算法项目和外部工具链打通的方式之一。6. 常见问题与调试心得6.1 程序卡住、跑飞了怎么办我见过不少初学者在验证大数时发现程序“卡住”其实大部分不是因为 3n1 猜想被推翻而是程序掉进了整数溢出后的死循环。排查顺序一般是先确认起始数是不是正整数。检查整数类型int就换成long long还不行就换__int128前提是编译器支持。如果用了递归检查递归深度是否过大。可以加一个计数器超过一定阈值就强制退出并打印当前 n看看它是否在重复出现。在关键位置加调试输出打印每次变换后的 n观察是否出现负数、越界、或者陷入某个局部循环。如果 n 开始出现负数基本可以断定是无符号或有符号整数溢出。如果 n 在某个区间里反复出现检查一下是不是你的奇偶判断写反了。我遇到过的最常见错误是把奇数写成n % 2 1然后用int存中间结果一旦溢出成负数这个条件就永远不成立程序就把负数当偶数不断除以 2结果跑到 -1 附近来回震荡看起来就是“死循环”。6.2 计算结果和网上资料不一样3n1 的“步数”定义有两个版本第一种从起始数到第一次出现 1 的变换次数。第二种把起始数本身也算进去的序列长度。网上很多数据表用的是第二种所以你在某些网站上看到“27 的序列长度为 112”而我用第一种算法是 111再一查发现你算出来 111 就对不上。这不代表程序写错只是统计口径不同。如果你要和其他资料对照先确认对方是否把起始数计入长度。工程上的建议是在函数注释里明确“本函数返回变换次数不包含起始数本身”避免之后自己都搞混。另外还有一个细节序列到达 1 之后严格按规则应该继续变成 4、2、1 循环。绝大多数实现把 1 当作终止条件不会继续循环。这也是一种约定。如果你想模拟“完整循环”终止条件可以改成n 4然后补上 4 → 2 → 1 的最后三步。但这个需求很少见一般没必要。6.3 从工程角度看这个“玩具项目”3n1 虽然只是个数学猜想但它作为 C 练习项目的价值远超一个循环本身。你可以在同一个项目里做几件进阶的事把get_steps改成并行版本用多线程分别计算 1 到 N 的多个分片最后汇总。用数组代替unordered_map做小范围内的缓存前提是 n 值不超过数组长度。在区间搜索时预先给已计算过的较小 n 建立一张查表降低递归深度。把__int128抽象成自定义类型封装加减乘除和输出这样代码在更多编译器上可移植。我个人的建议是先跑通单数验证再跑通区间搜索最后再考虑性能优化。不要一开始就追求“百万级跑得飞快”那样会把简单项目搞复杂反而失去练习意义。我自己写这个项目时最大的体会是“越是看起来简单的问题越要小心工程细节”。3n1 的数学规则没有难点但 C 的整数类型、递归深度、缓存策略、输入校验每一个都能单独拿出来写一篇经验总结。把这些细节点都处理好这份代码就不是一个“玩具”而是一个能真正用来验证数学猜想的实用工具。最后分享一个小技巧当你需要面对一个全新的递归算法但担心栈溢出时可以先用迭代版本跑一遍再用记忆化递归版本跑同样的数据对比结果是否一致。两个版本互相验证能帮你快速把“算法思路错误”和“代码实现错误”区分开来。这个方法我用了很多次处理 3n1 这类边界情况频出的问题尤其好用。