# [LeetCode 202] 关于快乐数的一个猜想

有一段时间没写博客了,今天看到快乐数,突然想起很久之前的一个猜想,就又翻了出来。

快乐数的特性是什么?该数字所有数位的平方和,得到的新数再次求所有数字的平方和,如此重复进行,最终结果一定为1。而我们知道,INT_MAX是21_4748_3647。如果想让次数尽可能多,那直觉应该是让所有数位的平方和最大。在INT_MAX的范围内,数位平方和最大的数字应该是19_9999_9999,而这个数的数位平方和是729。

这意味着什么?在INT_MAX的范围内,所有数字的数位平方和都不会超过这个数,也就意味着经过一次转换之后,INT_MAX范围内的所有快乐数都应该出现在729以内。在这个范围内的快乐数有:

1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, 103, 109, 129, 130, 133, 139, 167, 176, 188, 190, 192, 193, 203, 208, 219, 226, 230, 236, 239, 262, 263, 280, 291, 293, 301, 302, 310, 313, 319, 320, 326, 329, 331, 338, 356, 362, 365, 367, 368, 376, 379, 383, 386, 391, 392, 397, 404, 409, 440, 446, 464, 469, 478, 487, 490, 496, 536, 556, 563, 565, 566, 608, 617, 622, 623, 632, 635, 637, 638, 644, 649, 653, 655, 656, 665, 671, 673, 680, 683, 694, 700, 709, 716。

而这些快乐数“收敛”到1最多只需要10步(565和655)。所以,我猜想,INT_MAX以内的所有快乐数最多只需要11步就会收敛到1。由此,11次循环之后仍然没有收敛到1的数字一定不是快乐数。

bool isHappy(int n)
{
    int N = 11;
    while (N)
    {
        int new_n = 0;
        while (n > 0)
        {
            new_n += pow(n % 10, 2);
            n /= 10;
        }
        if (new_n == 1)
        {
            return true;
        }
        n = new_n;
        --N;
    }
    return false;
}

当然这只是一个猜想。

最后更新于: 6/25/2020, 2:10:06 PM