055. 吕克雷尔数(Lychrel numbers)

如果我们把\(47\)翻转过来并和其自身相加,结果是\(47+74=121\)是一个回文数。并不是所有的数都可以这么快的变成回文数,比如说:

$$ \begin{aligned} 349 + 943 &= 1292\\ 1292 + 2921 &= 4213\\ 4213 + 3124 &= 7337 \end{aligned} $$
也就是说349用了三次迭代才变成一个回文数。

尽管现在还没有人能够证明,但是普遍认为有些数字,比如说196永远不能用上面的方式产生回文数。那些不能通过翻转并相加的方式产生回文数称为吕克雷尔数。出于理论上的考虑以及为了解决这个问题,我们应该假设一个数是吕克雷尔数除非能够证明它不是。此外对于一万以下的数字以下信息已经确定:(1)这些数字要不可以在五十次迭代以内变成回文数;(2)要不就以目前的计算能力还无法让它们变成回文数。事实上,10677是第一个需要超过五十次迭代才能成为回文数的数,这个数是4668731596684224866951378664(需要五十三次迭代,总共二十八位数)。奇怪的是,有一些回文数它本身却是吕克雷尔数,第一个例子是4994。求一万以内有多少个吕克雷尔数?

分析:这道题的思路比较直接,我们在第四题已经编写了一个函数检测某个数字是否是回文数,这里可以直接拿来用。我们对一万以内的数字依次遍历,用其翻转加上它自身,如果在五十次迭代次数以内出现了回文数,则这个数不是吕克雷尔数,否则就是吕克雷尔数。最后统计吕克雷尔数的个数,即为题目所求。代码如下:

# time cost = 64.8 ms ± 229 µs

def is_lychrel(x):
    is_palindrome = lambda x : str(x) == str(x)[::-1]
    for _ in range(50):
        x += int(str(x)[::-1])
        if is_palindrome(x):
            return False
    return True

def main():
    ans = len([x for x in range(1,10000) if is_lychrel(x)])
    return ans