Collat z猜想Python-不正确的输出超过2万亿(仅!)



python-3.x algorithm (1)

这一行:

n = int(n/2)

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

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

当然2万亿也远低于浮动精度的2**53限制 - 但从N开始的Collat​​z序列经常变得很多,远远高于N.在2万亿左右的许多数字超过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 ,您要将最后一位或最后两位转换为0,这意味着您通常会切断链的大部分并将其替换为1或2个师。 但显然会有一些数字,你最终跳到的链比正确的链更长 。 事实上,我只花了3次尝试找到一个: 3,743,559,068,799,123应该采取326步,但它需要370。

我怀疑(但同样,我甚至无法想象如何证明)许多大数字将在375左右的同一范围内结束,因为它们(对数)变大了。 为什么? 好吧,只有这么多的数字你可以舍入到 - 而且大多数都可能在循环中彼此开始截断分割。 所以,让我们说几乎每个2**53附近的数字都有一个超过50的舍入周期长度,并且数百万个范围内的大多数数字在300多步中达到2**53范围......然后大多数都是最终会在375左右结束。(当然,这些数字是凭空捏造的,但你可以进行蒙特卡罗模拟,看看他们实际上离实际有多远......)

我在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.htmlhttp://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")




collatz