Python3.x Collat​​z Conjecture Python 超过 2 万亿的错误输出(仅限！)

这一行:

n = int(n/2)

…将n转换为浮点，将浮点除以2，然后通过丢弃小数部分将其转换回整数.

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

当然，2万亿远低于浮点精度的2**53极限，但从N开始的Collatz序列经常比N高得多.2万亿左右的许多数字都有超过2**53的序列，而低于2**53的数字很少.甚至有可能一整列从2万亿开始的数字超过2**53，但低于2**53的数字没有一个.但我不知道如何证明这一点，而不为每一个高达2万亿的数字建立完整的序列.(如果有证据的话，它可能会在很大程度上依赖于各种不同条件下猜想的现有部分证据，这些条件高于我的工资等级……)

无论如何，解决方案很简单:您想使用整数除法:

n = n // 2

以下是一个例子:

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

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

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时，你将把最后一位或最后两位转换成0，这意味着你通常会切断链的一大部分，并用1或2个分区来代替它.但很明显，会有一些数字，你最终跳到的链子比正确的数字高出longer.事实上，我只花了3次就找到了一个:3,743,559,068,799,123应该需要326步，但需要370步.

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