Collatz 猜想 Python - 超过 2 万亿的错误输出（仅！）
Collatz Conjecture Python - Incorrect Output Above 2 Trillion (Only!)
我在 Python3 中编写了一个计算 Collatz 猜想的基本脚本。它需要一个正整数作为输入，returns 直到序列下降到 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 `
正确的输出值基于此link：http://www.ericr.nl/wondrous/delrecs.html
对于超过 2 万亿的输入，我的脚本输出总是比正确输出少 1,052，但我不知道是什么原因造成的。
任何人都可以解释哪里出了问题，以及如何 update/fix 脚本以使其对所有输入都能正常工作？我认为 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")
这一行：
n = int(n/2)
… 将 n 转换为浮点数，将该浮点数除以 2，然后通过丢弃小数部分转换回整数。
对于最大 2**52 的整数，转换为浮点数是无损的，但对于更大的整数，它必须四舍五入到最接近的 53 位数字，这会丢失信息。
当然，2 万亿远低于浮点精度的 2**53 限制——但从 N 开始的 Collatz 序列经常比 N 高得多。2 万亿左右的许多数字一点也不难以置信有超过 2**53 的序列，而它下面的数字很少。甚至有可能从 2 万亿开始的一长串数字超过了 2**53，但没有一个数字低于它。但是我不知道如何在不为每个高达 2 万亿的数字构建整个序列的情况下证明这样的事情。 （如果有证明的话，估计会严重依赖现有的各种不同条件下猜想的部分证明，这超出了我的paygrade...）
无论如何，解决方法很简单：你想使用整数除法：
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 左右的相同范围内，随着它们（对数）变大而变短。为什么？好吧，您可以四舍五入的数字只有这么多，而且其中大多数可能彼此循环，您开始进行 t运行cating 除法。因此，假设 2**53 附近的几乎每个数字的舍入周期长度都超过 50，而万亿范围内的大多数数字在 300 多步后达到 2**53 范围……那么大多数他们最终会达到 375 左右。（当然，这些数字是凭空得出的，但是你可以做一个 Monte Carlo 模拟，看看它们实际上离现实有多远……）
我在 Python3 中编写了一个计算 Collatz 猜想的基本脚本。它需要一个正整数作为输入，returns 直到序列下降到 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 `
正确的输出值基于此link：http://www.ericr.nl/wondrous/delrecs.html
对于超过 2 万亿的输入，我的脚本输出总是比正确输出少 1,052，但我不知道是什么原因造成的。
任何人都可以解释哪里出了问题，以及如何 update/fix 脚本以使其对所有输入都能正常工作？我认为 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")
这一行：
n = int(n/2)
… 将 n 转换为浮点数，将该浮点数除以 2，然后通过丢弃小数部分转换回整数。
对于最大 2**52 的整数，转换为浮点数是无损的，但对于更大的整数，它必须四舍五入到最接近的 53 位数字，这会丢失信息。
当然，2 万亿远低于浮点精度的 2**53 限制——但从 N 开始的 Collatz 序列经常比 N 高得多。2 万亿左右的许多数字一点也不难以置信有超过 2**53 的序列，而它下面的数字很少。甚至有可能从 2 万亿开始的一长串数字超过了 2**53，但没有一个数字低于它。但是我不知道如何在不为每个高达 2 万亿的数字构建整个序列的情况下证明这样的事情。 （如果有证明的话，估计会严重依赖现有的各种不同条件下猜想的部分证明，这超出了我的paygrade...）
无论如何，解决方法很简单：你想使用整数除法：
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 左右的相同范围内，随着它们（对数）变大而变短。为什么？好吧，您可以四舍五入的数字只有这么多，而且其中大多数可能彼此循环，您开始进行 t运行cating 除法。因此，假设 2**53 附近的几乎每个数字的舍入周期长度都超过 50，而万亿范围内的大多数数字在 300 多步后达到 2**53 范围……那么大多数他们最终会达到 375 左右。（当然，这些数字是凭空得出的，但是你可以做一个 Monte Carlo 模拟，看看它们实际上离现实有多远……）