3n+1猜想，学名科拉兹猜想，也叫角谷猜想、冰雹序列。规则一句话就能说完：给你一个正整数 n，如果它是偶数，就除以 2；如果它是奇数，就乘以 3 再加 1。反复执行这个过程，不管从哪个数开始，最后都会掉进 4 → 2 → 1 这个循环里。这个“不管从哪个数开始”就是至今没人能证明的猜想，但计算机已经替我们验证了极其庞大的范围，目前没找到反例。
我这次用 C++ 把这个算法完整落地，顺便把“看似简单其实一踩一个准”的问题都梳理清楚：整数溢出、循环判断、缓存加速、区间统计，以及最终一份能直接交作业、能拿去跑实验的源码。适合刚学 C++、想用一个小项目练手的人，也适合想理解“算法思路 + 工程实现”怎么结合的人。读懂这一篇，你不仅会写 3n+1，还会明白为什么很多看似简单的递归算法，落地时总有一堆意想不到的坑。
1. 3n+1 猜想到底是什么
1.1 一个简单到反常的规则
先拿一个具体数字走一遍。假如从 6 开始：
- 6 是偶数，除以 2 → 3
- 3 是奇数，乘以 3 再加 1 → 10
- 10 是偶数，除以 2 → 5
- 5 是奇数，乘以 3 再加 1 → 16
- 16 是偶数，除以 2 → 8
- 8 是偶数，除以 2 → 4
- 4 是偶数，除以 2 → 2
- 2 是偶数，除以 2 → 1
整个过程是 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1，一共 8 步到达 1。这里用“步数”指从起始数变换到 1 所需要的操作次数。
它被叫作“冰雹序列”，是因为这个数列很不安分：上升、下降、再上升、再下降，像冰雹在高空云层里反复翻腾，但最终一定会落到地面上。比如从 27 开始，序列长度会拉到 111 步，中间最大值甚至可以冲到 9232，最后照样跌回 1。
换个角度看：如果我们定义一个函数 f(n)，那么整个 3n+1 就是在反复套用 f：
- n 为偶数时，f(n) = n / 2
- n 为奇数时，f(n) = 3n + 1
这几乎是最简单的分段函数了，没有任何复杂的数学操作。但正是这种简单让无数人着迷：一个小学三年级都能看懂的规则，却长期无法被严格证明“所有正整数都会走到 1”。
1.2 用 C++ 实现它的真正价值
有人会问：这么简单的算法，直接写几行 while 循环不就行了，值得专门用一篇博文来讲吗？
其实这里面的门道不少。纯数学爱好者喜欢用纸笔演算，但程序员的视角完全不同：我们关心的不只是“结果是不是 1”，还包括程序能不能在合理时间内跑完、会不会因为数字太大而溢出、能不能通过缓存把重复计算砍掉、以及如何把单个数验证扩展成区间统计。
3n+1 看起来只有一个循环，却能把 C++ 里几个重要概念全部串起来：
- 整数类型的溢出风险
- 循环终止条件的严谨性
- 递归、迭代、记忆化三种实现思路
- 性能优化：缓存、位运算、批量处理
- 输入输出与错误处理
这也是 C++ 特别适合实现 3n+1 的原因。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 步这就是 3n+1 的骨架。你甚至可以把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，直接拒绝非法输入。这不是多此一举。3n+1 猜想的研究对象是正整数，输入 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上限。
这个坑的根源在于：3n+1 的变换是“放大”和“缩小”在反复拉锯，奇数项会把数放大三倍多，而偶数项只能除以 2。一旦连续出现几个奇数，数值就会快速膨胀。
出现溢出时会发生什么？C++ 里有符号整数溢出是未定义行为，实际中常见的表现是：负数、错误的结果、甚至死循环。比如某个数在溢出后变成负数，程序再用n % 2 == 0判断时，可能永远不满足收敛条件。
这也是我坚持第一阶段就上long long的原因。C++ 标准只保证long long至少 64 位，而 64 位能覆盖绝大多数教学和验证场景。
3. 大数版实现：避开整数溢出
3.1 升级到 unsigned long long
如果你只想做“整数验证”，long long已经够了，但有些追求严谨的开发者会把类型换成unsigned long long。因为 3n+1 处理的全是正整数，用无符号类型在语义上更贴切，也能省下符号位，让正数范围比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 进阶版：__int128
GCC 和 Clang 都支持__int128这个扩展类型，它不是 C++ 标准的一部分，但在 Linux 环境下非常常用。它允许你使用 128 位整数，能让 3n+1 的验证范围大大扩展。
#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 为什么奇偶判断这么关键
写 3n+1 时，最核心的底层操作就是“判断奇偶”。判断对了，后续缩放才有意义；判断错了，整个序列就全乱套了。
很多新手喜欢写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_map<long 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_map<long 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_map<i128, 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 项，避免刷屏 vector<i128> 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 << "3n+1 猜想验证程序" << 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 -std=c++17 collatz.cpp -o collatz-O2让编译器做常见优化，包括循环优化和函数内联，对越大的搜索区间收益越明显。-std=c++17明确指定 C++17 标准，虽然这段代码在 C++11 下也能编译，但写上标准版本是好的工程习惯。-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(); }有了这个输出，你可以把 3n+1 序列丢进任何数据分析工具里观察规律，验证“上升比”“最大值”“偶奇交替模式”。这也是把算法项目和外部工具链打通的方式之一。
6. 常见问题与调试心得
6.1 程序卡住、跑飞了怎么办
我见过不少初学者在验证大数时发现程序“卡住”，其实大部分不是因为 3n+1 猜想被推翻，而是程序掉进了整数溢出后的死循环。排查顺序一般是：
- 先确认起始数是不是正整数。
- 检查整数类型：
int就换成long long，还不行就换__int128（前提是编译器支持）。 - 如果用了递归，检查递归深度是否过大。可以加一个计数器，超过一定阈值就强制退出并打印当前 n，看看它是否在重复出现。
- 在关键位置加调试输出，打印每次变换后的 n，观察是否出现负数、越界、或者陷入某个局部循环。
如果 n 开始出现负数，基本可以断定是无符号或有符号整数溢出。如果 n 在某个区间里反复出现，检查一下是不是你的奇偶判断写反了。
我遇到过的最常见错误是：把奇数写成n % 2 == 1，然后用int存中间结果，一旦溢出成负数，这个条件就永远不成立，程序就把负数当偶数不断除以 2，结果跑到 -1 附近来回震荡，看起来就是“死循环”。
6.2 计算结果和网上资料不一样
3n+1 的“步数”定义有两个版本：
- 第一种：从起始数到第一次出现 1 的变换次数。
- 第二种：把起始数本身也算进去的序列长度。
网上很多数据表用的是第二种，所以你在某些网站上看到“27 的序列长度为 112”，而我用第一种算法是 111，再一查发现你算出来 111 就对不上。这不代表程序写错，只是统计口径不同。
如果你要和其他资料对照，先确认对方是否把起始数计入长度。工程上的建议是：在函数注释里明确“本函数返回变换次数，不包含起始数本身”，避免之后自己都搞混。
另外还有一个细节：序列到达 1 之后，严格按规则应该继续变成 4、2、1 循环。绝大多数实现把 1 当作终止条件，不会继续循环。这也是一种约定。如果你想模拟“完整循环”，终止条件可以改成n == 4，然后补上 4 → 2 → 1 的最后三步。但这个需求很少见，一般没必要。
6.3 从工程角度看这个“玩具项目”
3n+1 虽然只是个数学猜想，但它作为 C++ 练习项目的价值远超一个循环本身。
你可以在同一个项目里做几件进阶的事：
- 把
get_steps改成并行版本，用多线程分别计算 1 到 N 的多个分片，最后汇总。 - 用数组代替
unordered_map做小范围内的缓存，前提是 n 值不超过数组长度。 - 在区间搜索时，预先给已计算过的较小 n 建立一张查表，降低递归深度。
- 把
__int128抽象成自定义类型，封装加减乘除和输出，这样代码在更多编译器上可移植。
我个人的建议是：先跑通单数验证，再跑通区间搜索，最后再考虑性能优化。不要一开始就追求“百万级跑得飞快”，那样会把简单项目搞复杂，反而失去练习意义。
我自己写这个项目时，最大的体会是“越是看起来简单的问题，越要小心工程细节”。3n+1 的数学规则没有难点，但 C++ 的整数类型、递归深度、缓存策略、输入校验，每一个都能单独拿出来写一篇经验总结。把这些细节点都处理好，这份代码就不是一个“玩具”，而是一个能真正用来验证数学猜想的实用工具。
最后分享一个小技巧：当你需要面对一个全新的递归算法但担心栈溢出时，可以先用迭代版本跑一遍，再用记忆化递归版本跑同样的数据，对比结果是否一致。两个版本互相验证，能帮你快速把“算法思路错误”和“代码实现错误”区分开来。这个方法我用了很多次，处理 3n+1 这类边界情况频出的问题尤其好用。
