非快乐数的判定方法及迭代循环必然性的证明问题

你观察得太准确了！所有非快乐数在反复计算各位数字平方和的过程中，必然会陷入循环，绝对不会无限制地生成全新的数字。下面我来给你拆解背后的逻辑：

首先先明确快乐数的定义：

定义：一个正整数如果反复计算其各位数字的平方和最终得到1，就称为快乐数，否则不是。

为什么非快乐数一定会进入循环？ #

核心原因可以分成两步来理解：

1. 迭代序列一定会进入一个有限的数字范围

对于任何正整数n，我们来分析它的各位平方和的上限：

• 如果n是k位数（k≥2），n的最大值是10^k - 1，而它的各位平方和最大为k * 9² = 81k。
• 当k≥3时，10^k - 1会远大于81k（比如3位数的最大值999，平方和是243，远小于999；4位数的9999，平方和是324，同样远小于原数）。
• 哪怕是两位数里最大的99，平方和是162（变成三位数），但下一次计算平方和就是1²+6²+2²=41，又回到了两位数的范围。

这意味着，不管你从多大的数开始迭代，最终都会落到一个不超过某个固定上限（比如1000）的有限数字集合里。

2. 有限集合内的迭代必然会出现重复（鸽巢原理）

既然我们的迭代序列只会在有限个数字里打转，根据鸽巢原理（抽屉原理）：当我们生成的数字数量超过这个集合的大小后，必然会遇到一个之前已经出现过的数字。

而每一步的计算都是确定唯一的——给定一个数字，它的各位平方和是固定的。所以一旦某个数字重复出现，后面的序列就会完全复刻之前的路径，形成循环，永远不会终止。

实际例子验证 #

就像你给出的例子：

• 数字2的迭代序列：2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，当4第二次出现时，循环就开始了。
• 数字3的迭代序列：3 → 9 → 81 → 65 → 61 → 37 → ...，当序列中出现37时，因为37已经在2的循环序列里了，所以后面就会跟着进入同一个循环。

事实上，所有非快乐数最终都会进入这个唯一的循环：4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，这是已经被证实的结论。

备注：内容来源于stack exchange，提问作者Yanjan. Kaf.