共计 2819 个字符,预计需要花费 8 分钟才能阅读完成。
一、只有两种结局
任取一个正整数,把它每一位上的数字分别平方,再加起来,就得到一个新的数。对这个新数重复同样的操作,一直算下去,会发生什么?
先以 7 为例:
7² = 49
4² + 9² = 16 + 81 = 97
9² + 7² = 81 + 49 = 130
1² + 3² + 0² = 1 + 9 + 0 = 10
1² + 0² = 1
到了 1 以后,再算下去还是 1(1² = 1),数字就不再变化了。
再换成 4 试试:
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
算了八步,又回到了 4。之后就会沿着这八个数一直转下去,永远停不下来。
那么换成别的数,结果会怎样?会不会有的数越算越大,或者进入另一个不同的循环?答案是都不会。每个正整数最后只有两种结局,要么到达 1,要么进入上面这个八步循环。能到达 1 的数叫 快乐数 ,进入循环的叫 不快乐数。1000 以内,快乐数有 143 个。这个结论为什么成立,第二部分会给出完整的证明。
这个结论来得有点突然,我们先多看几个例子。
从 2 开始:
2 → 4
2 只用一步就到了 4,直接进入了刚才的八步循环。
从 3 开始:
3 → 9 → 81 → 65 → 61 → 37
3 绕的路更远,经过 9、81、65、61 之后到达 37。37 正是循环里的一个数,所以 3 从循环的中途加入进去。
从 5 开始:
5 → 25 → 29 → 85 → 89
5 经过 25、29、85,在 89 处进入循环。
从 6 开始:
6 → 36 → 45 → 41 → 17 → 50 → 25
6 经过 36、45、41、17、50 之后到达 25,而 25 正是 5 的路径上的第二个数。从这里开始,6 的路径和 5 完全一样:25 → 29 → 85 → 89,最后也进入循环。
这说明了一个规律:两个起点只要碰到同一个数,之后的路径就完全相同。把所有数的路径画在一起,就像许多树枝汇进几根主干。
另外,数字的排列顺序和 0 都不影响结果。13、31、103、130 的各位平方和都是 10,所以它们下一步都会到达 10,再到达 1。在 1 到 10 之间,只有 1、7、10 是快乐数,其余 7 个数都会进入循环。
二、为什么会出现这种结果
事实上,如果用上述算法(把各位数字分别平方后相加)去处理一个大数,这个数一定会变小。这是因为这个数里的每一位最大的数字是 9,平方后是 81,所以每一位最多贡献 81。一个有 d 位的数算一步之后,结果最多是 81d。而这个 d 位数本身至少是 10^(d−1),也就是 1 后面跟着 d−1 个 0。把这两个量放在一起比较,可以看出它们增长的速度完全不同。采用上述算法计算的每一个数字所得到的结果,它的上限是 81d,和位数 d 成正比,位数每多一位,上限只增加 81。而这个数本身,位数每多一位,它的大小就扩大为原来的 10 倍。前者只是一位一位地往上加,后者却是成倍地放大。
在三位数时,前者还占上风,上限是 243,而三位数最小是 100。但从四位数开始,情况彻底反过来,四位数算一步最多得到 324,而四位数本身至少是 1000;五位数最多得到 405,本身却至少是 10000。位数越多,差距越悬殊。所以,任何四位及以上的数,每算一步都会变小,直到不超过三位为止。比如 9999 算一步就变成 324,9876543210 算一步就变成 285。
这个范围还可以继续收紧。三位数中,算出最大结果的是 999,结果为 243。所以任何三位数算一步后都不会超过 243。再看不超过 243 的数,其中算出最大结果的是 199,结果为 163。最后看不超过 163 的数,其中算出最大结果的是 99,结果为 162。
到这里,整个范围就被限制死了,从 1 到 162 之间的数,在计算后仍会落在 1 到 162 之内;而前面已经说明,任何数最终都会落进这个范围。于是,无穷多个起点的问题,就变成了一个有限的问题。只需把这 162 个数逐个算下去,就会发现:其中 26 个最终到达 1,其余 136 个进入那个八步循环,除此之外没有别的循环。由此证毕。
三、快乐数之树
反过来看哪些数能到 1。一步到 1 的数,各位只能是一个 1 加若干个 0,也就是 10、100、1000…… 再往外推,路径就开始分叉。所有快乐数组成一棵以 1 为根的树,一个数走到根需要的步数叫它的 " 高度 "。10 的高度是 1,13 是 2,7 和 70 是 5。路径可以先升后降,比如 130 比 100 大,但也在这棵树里。
树的高度没有上限。由 37 个 1 组成的数会落到 37,这个办法对任何数都适用,所以每一层都能再往外延伸。各高度的最小数依次是 1、10、13、23、19、7,然后突然跳到 356 和 78999。高度 8 的数第一步必须落在一个高度 7 的数上,最小的目标是 78999。每位最多贡献 81,所以至少需要 977 位:3、7、8、8 后面跟 973 个 9。验算一下:9 + 49 + 64 + 64 = 186,973 × 81 = 78813,两者相加正好是 78999。高度 9 的最小数更夸张,位数大约是 4.7 × 10^974,远远超过可观测宇宙里的原子总数。
四、不快乐数
1000 以内的 857 个不快乐数都进入同一个循环,只是进入的位置不同:从 89 进入的最多,有 362 个;从 42 和 20 进入的最少,只有 12 个和 9 个。进入循环最慢的是 269,要走 11 步才到 89。由此有一个快速判断的办法:一直算下去,看先出现 1 还是 4。
快乐数在 1000 以内占 14.3%,一万以内占 14.4%,一百万以内又回到 14.3% 左右,看上去稳定在七分之一。一个数是不是快乐数,只看它第一步的平方和。所以不用逐个检查,只要统计 k 位数字串得到每种平方和的个数,就能精确算出 10^k 以内的比例。算出来的结果出人意料:到 10^18 附近降到约 11.8%,到 10^40 附近回升到接近 16%,到 10^403 附近升到约 18.6%,之后又回落。2013 年,贾斯汀·吉尔默证明这种波动永远不会停:比例会无穷多次超过 18.5%,也会无穷多次低于 11.4%。所以快乐数没有一个固定的密度,它占多少,取决于你数到哪里为止。
六、更多花样
- 连续快乐数:最早的一对是 31 和 32,最早的三个连续是 1880 到 1882。第一组七个连续快乐数从一个 25 位数开始。2000 年,El-Sedy 和 Siksek 证明了任意长度的连续串都存在。
- 快乐素数:7、13、19、23、31…… 一百万以内大约 14% 的素数是快乐数。
- 换进制:二进制里平方和就是 1 的个数,总会让数变小,所以所有数都是快乐数。四进制里,轨道被限制在 27 以内,逐个检查后也全部是快乐数。这样的进制叫 " 快乐进制 ",目前只知道 2 和 4 两个,5 亿以内都没有找到别的,还有没有其他快乐进制至今没有答案。
十进制不是快乐进制,所以才有两种结局:要么到达 1,要么陷入 4、16、37、58、89、145、42、20 的循环。