Lychrel数算法

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

然后，我们可以创建一个https://wiki.python.org/moin/Generators，生成您描述的一系列数字：

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

但是，否则它将继续下去，直到你的内存耗尽！

Answer 2

关于数学中链长分布的一个小实验：

f[n_] := NestWhileList[# + FromDigits@k &, n,
                       (# != (k = Reverse@#)) &@IntegerDigits[#] & ] // Length

(* remove known lychrel candidates *)
list = f /@  Complement[Range@1000, {196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 
                                     887, 978, 986}];

Histogram@list

​

​

到3700岁为止：

​

​

Answer 3

首先，我们有一个函数来反转一个数字的数字：

def rev(n, r=0):
    if n == 0: return r
    return rev(n // 10, r*10 + n%10)

然后，我们可以用它来确定一个数字是否是Lychrel数；在这里，我们返回否定这个数字的Lychrel-性的链，或者一个单例列表来表示这个数字是Lychrel：

def lychrel(n, bound=1000):
    r = rev(n); chain = [n]
    while bound > 0:
        n += r; r = rev(n)
        chain.append(n)
        if n == r: return chain
        bound -= 1
    return [chain[0]]

下面是一些示例：

>>> lychrel(196)
[196]
>>> lychrel(281)
[281, 463, 827, 1555, 7106, 13123, 45254]

你可以在我的博客上读到更多关于Lychrel数字的信息。

编辑：在受到Tony 66的挑战后，做了我向他提议的计时测试。你可以在http://ideone.com/5gTbSH看到他们。我的递归函数只使用整数，比转换为字符串和返回的函数快30%左右。更快的是只使用整数的函数的迭代版本。

我通常是一个Scheme程序员，而不是Python程序员，我对迭代版本和递归版本之间的区别感到惊讶，这是因为Python的函数调用开销。当我在Scheme中做同样的实验时，迭代版本和递归版本基本上没有区别，这是有意义的，因为递归在尾部位置，因此本质上是迭代的。