1

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

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

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

重复直到获得n新的直到。xTrue

有什么方法可以在 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个步骤。

4

4 回答 4

3

首先，定义两个方便的函数（你可以自己做！）：

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

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

然后我们可以创建一个生成器来生成您描述的一系列数字：

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

但否则它将继续，直到你的内存用完！

于 2015-09-01T16:34:08.223 回答
2

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

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 数字的更多信息。

编辑：在受到托尼萨福克 66 的挑战后，我做了我向他提出的计时测试。你可以在http://ideone.com/5gTbSH。我的仅使用整数的递归函数比他的转换为字符串并返回的函数快约 30%。Faster 仍然是仅使用整数的函数的迭代版本。

我通常是一名 Scheme 程序员，而不是 Python 程序员，我对迭代和递归版本之间的差异感到惊讶，我将其归因于 Python 的函数调用开销。当我在 Scheme 中进行相同的实验时，迭代和递归版本之间基本上没有区别，这是有道理的，因为递归处于尾部位置，因此本质上是迭代的。

于 2015-09-01T18:44:09.263 回答
2

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

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 都是一样的：

数学图形

于 2015-09-01T17:26:23.173 回答
1

我的代码不像 jonrsharpe 那样 Pythonic，但更接近您的示例。首先定义一个我叫 palindrome.py 的文件：

def reverseInt(x):
    """Return the digit-reversed version of integer x (digits in decimal)."""
    #Convert to string, because strings are iterable.  Obtain a reverse
    #  iterator to the characters.
    Rx = reversed(str(x))
    #Obtain reversed string by joining with no intervening characters
    Rx = "".join(Rx)
    #Switch back to integer
    Rx = int(Rx)
    return Rx

def iteration(x):
    """Return a 2-tuple (n, done) where n is the result of one iteration of
    the palindrome search, and done is a boolean flag indicating whether n is
    a palindrome."""
    Rx = reverseInt(x)
    n = x + Rx
    Rn = reverseInt(n)
    return n, n==Rn

def depth(x):
    """Return a 2-tuple (y, numIter) where y is a palindrome and numIter
    is the number of palindrome iterations needed to obtain y from x."""
    numIter = 0
    if x == reverseInt(x):
        return x, numIter
    done = False
    while not done:
        x, done = iteration(x)
        numIter += 1
    return x, numIter

现在运行 python

python
>>> import palindrome as pD
>>> #pD is only for brevity, I'm being a lazy typist
>>> pD.iteration(79)
(176, False)
>>> pD.depth(79)
(44044, 6)
于 2015-09-01T16:50:15.580 回答