python - 利克瑞尔数算法

Question

最近着迷于寻找 Lychrel 和回文数作为娱乐数学。

对于不知道的人，手动对号码执行此检查的过程如下。

1. 设 x 为某个数字。
2. 令R(x)为反写的x对应的数。
3. 令 n = x + R(x)
4. 如果 n == R(n)，则返回 True，否则返回 False。

重复 n 作为新的 x，直到获得 True。

有没有办法在 Python 中自动执行此操作？我可以在其中输入一个数字，它会告诉我它的倒数之和是否是回文。此外，我想看看达到这个数字需要多少步。

例子:

令 x 为 79。79 + 97 为 176，这不是回文，因此我们得到 False。

现在设 x 为 176。176 + 671 为 847，这不是回文，所以我们得到 False。

我们继续:

• 847 + 748 == 1595
• 1595 + 5951 == 7546
• 7546 + 6457 == 14003
• 14003 + 30041 = 44044

这是我们最终遇到回文的地方。共 6 个步骤。

Answer 1

首先，定义两个方便的函数(你可以自己做!):

def is_palindrome(number):
    """Whether the number is a palindrome."""
    raise NotImplementedError

def reverse(number):
    """The number reversed, e.g. 79 -> 97."""
    raise NotImplementedError

然后我们可以创建一个generator产生您描述的一系列数字:

def process(number):
    """Create the required series of numbers."""
    while True:
        yield number
        if is_palindrome(number):
            break
        number += reverse(number)

例如:

>>> list(process(79))
[79, 176, 847, 1595, 7546, 14003, 44044]
# 0    1    2     3     4      5      6

---

确定一个数是否是 Lychrel 数比较棘手 - 显然，当我们的生成器用完时，判断它是否是微不足道的:

def is_lychrel(number):
    """Whether the number is a Lychrel number."""
    for _ in process(number):
        pass
    return False

你可以测试我们是否重复一个数字(如果有一个循环，它永远不会到达回文):

def is_lychrel(number):
    """Whether the number is a Lychrel number."""
    seen = set()
    for num in process(number):
        if num in seen:
            return True
        seen.update((num, reverse(num)))  # thanks @ReblochonMasque
    return False

否则它会一直持续到内存不足!