python - Collat​​z Conjecture Python - 超过 2 万亿的错误输出(仅限!)

Question

我用 Python3 编写了一个计算 Collat​​z 猜想的基本脚本。它接受一个正整数作为输入，并返回步数，直到序列下降到 1。

我的脚本非常适合小于~2 万亿的任何整数输入，但高于此阈值的输出太小了。

例如，这里有一些输入、我的脚本的输出和实际正确的输出:

Integer Input          Script Output     Correct Output
   989,345,275,647        1,348             1,348 
 1,122,382,791,663        1,356             1,356 
 1,444,338,092,271        1,408             1,408 
 1,899,148,184,679        1,411             1,411 
 2,081,751,768,559          385             1,437 
 2,775,669,024,745          388             1,440 
 3,700,892,032,993          391             1,443 
 3,743,559,068,799          497             1,549 `

正确的输出值基于此链接:http://www.ericr.nl/wondrous/delrecs.html

对于超过 2 万亿的输入，我的脚本输出总是比正确输出少 1,052，但我不知道是什么原因造成的。

谁能解释问题出在哪里，以及如何更新/修复脚本以使其适用于所有输入？我认为 Python 能够毫无问题地接受任意大的数字...

谢谢!

# Python Code for the Collatz Conjecture
# Rules: Take any integer 'n' and assess:
# If integer is even, divide by 2 (n/2)
# If integer is odd, multiply by 3 and add 1 (3n+1)
# Result: a list of all steps until 'n' goes down to 1

while True:
    print("Please enter a positive integer:")
    n = input("")
    if n == 'q':
        print("Until next time ...\n")
        break
    try:
        n = int(n)
        if n > 0:
            i = 0
            while n > 1:
                if n % 2 == 0:
                    n = int(n/2)
                    i += 1
                else:
                    n = int((3*n)+1)
                    i += 1
            print("# of steps to reach '1' = ", str(i), "\n")
        else:
            print("Sorry, that's not a valid entry. Please try again!\n")
    except ValueError:
        print("Sorry, that's not a valid entry. Please try again!\n")

Answer 1

这一行:

n = int(n/2)

... 将 n 转换为 float ，将该 float 除以 2，然后通过丢弃小数部分转换回 int。

对于小于等于 2**52 的整数，转换为 float 是无损的，但对于更大的整数，它必须四舍五入到最接近的 53 位数字，这会丢失信息。

当然，2 万亿远低于 2**53 浮点精度的限制——但从 N 开始的 Collat​​z 序列经常比 N 高得多。大约 2 万亿的数字有超过 2**53 的序列，而低于它的数字很少。甚至有可能从正好 2 万亿开始的一长串数字超过 2**53 但没有一个低于它的数字。但是我不知道如何在不为每个高达 2 万亿的数字构建整个序列的情况下证明这样的事情。 (如果有证明，可能会严重依赖现有的猜想在各种不同条件下的部分证明，这超出了我的工资等级……)

不管怎样，解决方法很简单:你要使用整数除法:

n = n // 2

---

这里有一个例子来演示:

>>> n = 2**53 + 3
>>> n
9007199254740995
>>> int(n/2)
4503599627370498
>>> n//2
4503599627370497

---

要验证您的代码中是否确实发生了这种情况，请尝试以下操作:

def collatz(n):
    overflow = False
    i = 0
    while n > 1:
        if n > 2**53:
            overflow=True
        if n % 2 == 0:
            n = int(n/2)
            i += 1
        else:
            n = int((3*n)+1)
            i += 1
    return i, overflow

if __name__ == '__main__':
    import sys
    for arg in sys.argv[1:]:
        num = int(arg.replace(',', ''))
        result, overflow = collatz(num)
        print(f'{arg:>30}: {result:10,} {overflow}')

当我运行这个时:

$ python3 collatz.py 989,345,275,647 1,122,382,791,663 1,444,338,092,271 1,899,148,184,679 2,081,751,768,559 2,775,669,024,745 3,700,892,032,993 3,743,559,068,799

……它给了我:

           989,345,275,647:      1,348 False
         1,122,382,791,663:      1,356 False
         1,444,338,092,271:      1,408 False
         1,899,148,184,679:      1,411 False
         2,081,751,768,559:        385 True
         2,775,669,024,745:        388 True
         3,700,892,032,993:        391 True
         3,743,559,068,799:        497 True

所以，我们在与得到错误答案的情况完全相同的情况下通过了 2**53。

为了验证修复，将 int(n/2) 更改为 n//2:

           989,345,275,647:      1,348 False
         1,122,382,791,663:      1,356 False
         1,444,338,092,271:      1,408 False
         1,899,148,184,679:      1,411 False
         2,081,751,768,559:      1,437 True
         2,775,669,024,745:      1,440 True
         3,700,892,032,993:      1,443 True
         3,743,559,068,799:      1,549 True

---

那么，为什么它总是以相同的数量关闭？

嗯，这主要是您碰巧使用的特定数字的巧合。

当您通过 3n+1 传递 2**53 时，您将把最后一位或最后 2 位转换为 0，即意味着您通常会切断链条的大部分并仅用 1 或 2 个分区替换它。但显然会有一些数字，您最终跳转到的链比正确的链长。事实上，我只用了 3 次尝试就找到了:3,743,559,068,799,123 应该需要 326 步，但需要 370 步。

我怀疑(但同样，我什至无法想象如何证明)许多大数字最终会在 375 左右的相同范围内，随着它们(对数)变大而变短一些。为什么？好吧，您可以四舍五入的数字只有这么多——而且它们中的大多数可能彼此处于循环中，您开始进行截断除法。所以，假设 2**53 附近的几乎每个数字都有一个超过 50 的舍入周期长度，而万亿范围内的大多数数字都达到了 2**53 范围在 300 多步……然后大多数最终会在 375 左右。(当然，这些数字是凭空捏造的，但您可以进行蒙特卡洛模拟，看看它们实际上离现实有多远是……)