这个系列聊到第三篇我想把一个特别耐玩的数列摊开来讲3n1数列很多人也叫它冰雹数列。规则简单到一句话就能说完——遇到偶数就除以2遇到奇数就乘3再加1然后重复这个过程。你会得到一个忽大忽小、看起来毫无章法却几乎总是跌跌撞撞滑向1的数列。我最早是在纸上乱画时碰到它的。随手写一个7按规则一步步算下去7变成2222变成1111变成3434变成17……一路折腾到了52又慢慢掉回1。当时我盯着那串数字看了半天心里只有一个疑问凭什么所有数最后都会掉到1这个疑问到现在都还没有被完整回答但它已经让无数人玩了几十年。这篇文章专门聊聊这个数列的定义、性质、几段经典航程以及你可以怎样亲手验证它。1. 这个数列的规则只有一行却值得玩一下午1.1 从“偶数除以2、奇数乘3加1”说起序列的构造方式不需要任何高深数学知识。给定一个正整数比如n然后按下面这条规则不断生成下一个数如果当前数是偶数就除以2如果当前数是奇数就乘3再加1重复直到变成1为止。比方说从6出发6是偶数除以2得到33是奇数乘3加1得到1010是偶数除以2得到55是奇数乘3加1得到1616是偶数一路除以2得到8、4、2、1。整条航程写出来就是6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1这条航程并不长总共用了8次变换。但如果你把起始值换成7事情立刻变得不一样。7是奇数先变成22然后一路走成11、34、17、52、26、13、40、20、10、5、16、8、4、2、1。航程拉长到了16步最高还冲到了52。同样是两位数一个安安静静地到1另一个绕了一大圈才回家。这就是这个数列的第一个有趣之处规则对你毫无隐瞒但结果却很难一眼看穿。你几乎没法凭起始大小判断它要飞多久、飞多高。1.2 前十个自然数的航程档案为了更直观地感受这种“没规律”我把从1到10的起始值全部跑了一遍得到下面这张小表。每一行记录的是“从起始值开始需要多少次变换才能到1”以及“整条航程里出现的最大值”。起始值到1所需的变换次数航程最高点101212371642455166816716528389195210616注意几个细节。第一个是6的航程虽然比5长但最高点反而和5一样都是16。第二个是9的航程高达19步比7还多但最高点仍然是52。第三个是10明明比6大却只用了6步就到1。这说明“高度”和“步数”是两回事都跟起始数的大小没有简单关系。这张表里最不省心的就是7和9。7飞到529也飞到52好像52成了一个小范围内过不去的坎。但如果把起始值继续往上推这个“坎”很快就会被突破。1.3 三个第一印象跑完前十个自然数你会留下三个很深的印象。第一几乎所有数的航程都能到1。至少在这个小范围里没有看到一个例外。第二偶数的路径通常很温和奇数的路径往往更曲折因为奇数乘以3加1之后会明显膨胀。第三航程里经常出现“冲高、回落、再冲高、再回落”的节奏像一段没有任何乐谱的即兴演奏。这三个印象会伴随你很久。它们也是理解这个数列所有后续性质的起点。2. 奇偶、模4与净缩小这个数列的“地心引力”2.1 奇数乘3加1其实是给自己造了一个偶数很多人第一次看到规则时会觉得奇怪奇数为什么要乘3再加1乘3会变大加1后变成偶数然后又会被除以2。从局部看这一步似乎是“先变大再变小”整体上应该互相抵消才对。但仔细想一下会发现乘3加1之后得到的数不仅能被2整除有时候还能被2多次整除。换句话说奇数经过一次变形后往往能连续除以好几次2。比如从5出发5乘3加1得到16而16能被2整除4次直接一口气化为1。这就是5只花了5步就到1的原因。所以奇数转偶数的这一步本质上不是“涨一截再跌一截”而是“涨一截之后可能跌好几截”。多次跌通常能抵消一次涨。2.2 一类奇数注定先缩水另一类注定先膨胀如果把这个过程再细分一点可以用模4来分类。任何一个奇数要么形如4k1要么形如4k3。先看形如4k1的奇数。比如5、9、13、17这种数乘3再加1之后得到的12k4一定是4的倍数。这意味着它至少能被4整除也就是可以连续除以2至少两次。5变成16一口气除以2除到113变成4040除以2得到20再除以2得到10还能继续往下走。这类奇数经过一轮操作后通常会明显缩水。再看形如4k3的奇数比如3、7、11、15。它们乘3加1之后得到12k10只能被2整除一次剩下的部分仍然是奇数。7变成2222除以2得到11而11还会继续乘3加1。所以这类奇数在一轮操作之后大概率是先涨上一截。我们看到7的航程冲到52、9的航程也冲到52正是因为9虽然属于4k1但它后面的变形过程中出现了大量4k3型的奇数于是高点不断被刷新。这个模4的视角特别有用。它可以解释为什么某些数会在开头快速飙升也可以解释为什么整体趋势又是向下的——因为在自然数里形如4k1的数和形如4k3的数一样多但4k1类奇数在变形后缩水更猛。2.3 平均来看它在慢慢变小一个不严谨的直觉把上面的观察再往前推一步可以得到一个粗浅的平均模型。一个奇数n经过“乘3加1后再不断除以2”的组合操作后通常可以写成(3n 1) / 2^k其中k是连续除以2的次数。对于一个随机出现的3n1来说k1的情况大约占一半k2的情况大约占四分之一k3的情况大约占八分之一以此类推。这样一来k的平均值接近2。如果k平均为2那么一轮操作下来数的大小大约是原来的(3n1)/4粗略地说就是0.75n多一点。偶数本身就在缩水奇数平均也在缓慢缩水。这就形成了一股“地心引力”把绝大多数航程都拽向低处。但必须强调这个说法只是直觉不是证明。因为平均值为0.75不代表每一条具体的航程都会按这个平均值走。有些数会在很长一段区间里连续经历k1的情况比如经典的27号航程会在半路冲到一个让人吃惊的高度。真正的数学证明远比这种平均直觉要难得多。3. 27号航程一架让人捏把汗的数字过山车3.1 从草稿纸到电脑27到底飞了多远如果说7和9的航程只是小打小闹那么27的航程就是真正的过山车。我第一次完整跑完27的全过程时在纸上写满了大半个页面最后确认它确实停在了1但还是不太敢相信中间居然能飞那么高。27的前几步是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 …从27开始它并没有直线冲向最高点而是跌跌撞撞地爬升。你注意看前半段经常会看到一个数翻倍式膨胀然后又被砍半接着继续膨胀。到了第77步它摸到了整条航程的最高点9232。9232这个数本身不算惊人但放在27的航程里就非常离谱。一个小小的两位数居然在飞行途中膨胀到了接近一万的高度。更离谱的是它从9232回落之后并没有一路顺畅地奔1而是再次经过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才最终落地。整段航程一共111步。也就是说27花了77步爬到最高点又花了34步滑翔降落。它在空中飞行的时间比很多大得多得多的数都要长。3.2 111步和9232这些路标的含义111步和9232这两个数字几乎成了这个数列爱好者圈里的“通用暗号”。只要你说出27和9232对方就知道你聊的是哪条航线。这两个数字之所以有意义是因为它们打破了很多人对“小数字很快就能到1”的直觉。27很小但它的飞行时间非常长。如果你在表格里按步数排序前一万个自然数里27很长一段时间都站在显眼的位置上。可以说它是一个教科书级别的反例专门用来击碎“越小的数越早到1”这种幼稚猜想。更值得注意的是27的高点9232。在它之前所有更小的自然数都没有在任何航程里到达过这个高度。高度纪录这种东西并不完全由起始值大小决定。27成了一个小范围内的“高度保持者”直到后来被更大但不是特别大的数打破。这些路标还说明了另一件事这个数列的航程不是单调的而是充满了“假希望”。你会看到某个数连续几次被除以2看起来马上就要平稳降落了结果突然又冒出一个奇数把它重新顶上去。27在回落过程中遇到2323变成7070变成3535又变成106就是这种反复无常的典型片段。3.3 更大的世界里纪录还在不断刷新跳出个位和两位数把视野放到十万以内步数纪录保持者变成了77031。它的总步数大约是350步航程最高点超过21万。再把范围扩到一百万以内纪录保持者则是837799总步数大约是524步。这些数字很容易让人产生一种“再跑大一点就能找到反例”的错觉。但事实是人们在已经检查到的巨大范围内始终没有发现一个不能回到1的起始值。每个新纪录的出现都只是把“已经验证的范围”往外推进了一点并没有从根本上改变问题的性质。所以跑数据这件事玩起来很爽但它更像是在给猜想“做体检”而不是在“证明”它。体检千万次健康只能说暂时没发现问题不等于未来永远不会出问题。4. 把猜想的验证交给代码实操与结果4.1 十几行Python跑出完整航程这种大量重复的变换靠手算根本扛不住但用程序来做就轻松多了。如果你想亲眼看一条航程的完整走势最直接的办法是写一个函数让它把从起点到1的每一个数都记录下来。下面是一个很简洁的Python实现def collatz_seq(n): seq [n] while n ! 1: if n % 2 0: n n // 2 else: n 3 * n 1 seq.append(n) return seq调用方式也很直白seq collatz_seq(27) print(len(seq) - 1) # 111变换次数 print(max(seq)) # 9232航程最高点如果你装了matplotlib还能顺手画一条折线图import matplotlib.pyplot as plt plt.plot(collatz_seq(27)) plt.title(Collatz sequence starting from 27) plt.show()画出来的图会非常直观一条曲线先是波浪式地爬升冲到一个尖峰然后七弯八绕地落下去最后在1附近消失。我第一次看到这幅图时脑子里冒出来的词就是“冰雹”——云层里的冰雹就是反复上升、下降最后落到地面这条曲线的形态和它如出一辙。4.2 加个缓存让十万个数一起接受检查如果只是看一个27代码已经够用了。但更常见的玩法是批量验证从1到某个上限把每个数的航程步数都算出来看看谁最长、谁最高。这时候直接写循环会很慢因为很多数在飞行的过程中会撞进“已经被算过”的路径里重复计算纯粹浪费资源。解决办法是加一个缓存把已经算过的起始值的步数记住。Python里可以直接用自带的functools.lru_cachefrom functools import lru_cache lru_cache(maxsizeNone) def collatz_steps(n): if n 1: return 0 if n % 2 0: return 1 collatz_steps(n // 2) return 1 collatz_steps(3 * n 1) for n in range(1, 100001): collatz_steps(n) print(collatz_steps(77031)) # 大约350加缓存的原理很简单。假设你已经知道13的步数是9那么当某个数在飞行中遇到13时就不用继续往下算了直接在总步数里加上9就行。这种“记忆化搜索”在算法题里很常见放在这个数列上效果也一样明显。十万个数批量跑用不了一秒一百万个数也就是几秒的事。如果你担心递归深度也可以换成显式栈加字典的写法。不过我在十万到一百万的范围内测试时递归深度都在安全值以内直接用lru_cache最省事。4.3 我跑出来的几个反直觉结论批量验证之后你会得到几个非常反直觉的结论。第一步数最多、飞得最高的往往不是那些很大的数而是中不溜秋的数。十万以内步数冠军是77031而不是100000百万以内步数冠军是837799。大数不一定折腾小数的飞行时间也可能非常长。第二不同起始值之间的步数差异极其悬殊。9只需要19步而77031需要大约350步两者之间差了一个数量级。第三无论是十万还是一百万所有起始值最终都回到了1。跑完这些数据后你会对“3n1猜想”产生一种复杂的心情一方面觉得它大概率是真的另一方面又知道自己手里的这些证据根本不足以给出数学上的定论。5. 改一个符号或一个常数剧情立刻失控5.1 把加1改成减1多循环的世界想真正理解3n1的特殊性最好的办法不是继续加码验证而是去改规则。改动越小对比越直观。先把规则里的“加1”改成“减1”。也就是说偶数除以2奇数乘3减1。从5开始5 → 14 → 7 → 20 → 10 → 5它绕了一圈回到5然后陷入一个长度为5的循环。从17开始又会进入另一个循环17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17这个循环更长绕了18个数才回到起点。再加上1到2再到1的短循环这条“3n-1规则”下面至少坐着三套不同的循环系统。起点不同命运完全不同有的直接掉进1有的陷进5循环有的陷进17所在的循环。这个实验非常震撼。仅仅把加号改成减号一个看起来“应该差不多”的系统就完全变了样。原来的“所有数似乎都奔向1”的秩序瞬间被多个环环相扣的小循环取代了。5.2 为什么偏偏是3n1站得这么稳如果把常数改得更多情况会更加混乱。比如偶数除以2、奇数乘3再加3从5出发就会陷入6、3、12的循环如果把乘数改得更大轨迹往往直接膨胀向上再也看不到回落的迹象。这些实验指向同一个结论3n1这个组合恰好站在一个脆弱的临界点上。乘3带来的膨胀被后续的连续除以2抵消加1带来的偏移又没有大到破坏整体收缩的趋势。整条规则像一只走钢丝的杂技演员向左一点会跌进多重循环向右一点会直接飞走。正因如此这套规则才能在“局部膨胀”和“整体收缩”之间维持一种微妙的平衡。但所谓“整体收缩”只是统计直觉不是严格证明。你无法用“平均来说会缩小”来解释为什么每一个自然数都一定会回到1。5.3 已经知道的部分和不知道的部分研究这个数列多年之后人们其实已经积累了不少确定性的结论。比如所有形如2的幂的数显然会直接除到1再比如某些特定模类的数值可以用数论方法直接证明会归位又比如在计算机检查过的庞大范围内没有出现反例。但整个问题最核心的一步依然悬着用什么方法可以严格证明所有正整数都不会陷入非4、2、1的循环也不会一路无界地膨胀上去。吸引人的地方恰恰在这里——这个问题的门槛极低任何人都能理解但它却让无数聪明人想破脑袋。它像一面镜子照见了人类对“简单规则背后全局行为”的理解是多么有限。所以围观这个问题的正确姿势是多观察、多记录、多验证但不要轻易说“我证明了它”。数学的严谨性不是多跑几个例子就能填补的。6. 玩数列玩出的三点心得6.1 规则“简单”不等于结论“简单”我这些年见过不少项目也读过不少算法越来越觉得“简单”和“容易”是两码事。3n1数列是最好的教材之一规则连一个小学生都能上手但它的性质却让专业研究者都头疼。这个道理放到日常生活中也一样。很多看似简单的问题背后往往藏着非常复杂的结构。如果你看到一个问题规则很简单就先武断地认定它“没什么难的”那大概率会在深入之后碰一鼻子灰。6.2 观察、记录、验证然后对“证明”保持敬畏验证这个数列最好的方式就是老老实实把数据跑出来记录航程、步数和最高点。你跑得越多就越能理解“证据”和“证明”之间的差距。人的直觉很容易被少量样本带偏。如果我只看1到10的数据会觉得“到1的规律真明显”但如果只看3n-1的例子又会觉得“数字系统天生适合形成循环”。两个系统如此相似结论却天差地别。这提醒我在做任何判断之前先搞清楚自己手里的证据到底能支持到哪一步。6.3 这是一个绝佳的编程入门素材如果你身边有朋友正在学编程或者你自己想找一个小项目练手我强烈推荐用这个数列当素材。它不需要任何前置知识却能覆盖循环、递归、缓存、数据可视化、性能优化这些重要话题。想做进阶一点可以统计不同区间里的步数分布看看是不是呈现某种形状也可以画一张散点图把步数和起始值的关系摆出来。最后再改一下规则试试3n-1、5n1、3n3观察系统如何从有序走向复杂。我在实际玩这个数列时最常做的事情不是研究它的证明而是拿它当一块试验田测试各种程序写法和分析思路。如果你也想找点有意思的东西填满一个下午不妨从27开始亲手按下运行键看看那条曲线是怎么冲到9232又落回1的。那种亲眼看着数字翻滚的感受只有亲自试过才知道。