Ответ 1
Эта строка:
n = int(n/2)
... преобразует n в float, делит это float на 2, затем преобразует обратно в int, отбрасывая дробную часть.
Для целых чисел до 2**52 преобразование в float без потерь, но для чего-либо большего оно должно округляться до ближайшего 53-битного числа, которое теряет информацию.
Разумеется, 2 трлн. Хорошо под этим пределом 2**53 для точности поплавка, но последовательность Collatz, начинающаяся с N, часто идет намного, намного выше 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
Итак, почему он всегда отключается на одну и ту же сумму?
Ну, это в основном просто совпадение конкретных чисел, которые вы используете.
Когда вы передаете 2**53 через 3n+1, вы собираетесь преобразовать либо последний бит, либо последние 2 бита в 0, что означает, что вы обычно отсекаете большую часть цепи и заменяете ее только 1 или 2 дивизии. Но, очевидно, будет несколько цифр, где цепочка, в которую вы в конечном итоге прыгаете, длиннее правильной. На самом деле мне потребовалось всего 3 попытки найти один: 3 3,743,559,068,799,123 должны принимать 326 шагов, но это занимает 370.
Я подозреваю (но опять же, я даже не могу себе представить, как доказать), что многие большие числа в конечном итоге окажутся в том же диапазоне около 375, немного короче, поскольку они получат (логарифмически) больше. Зачем? Ну, есть только так много чисел, которые вы можете объединить, и большинство из них, вероятно, находятся в цикле друг с другом, вы начинаете делать усечение деления. Итак, допустим, что почти каждое число около 2**53 имеет длину цикла округления более 50, а большинство чисел в диапазоне триллионов достигают 2**53 диапазона чуть более 300 шагов... тогда большинство из них собирается в конечном итоге около 375. (Конечно, эти цифры выведены из воздуха, но вы можете сделать симуляцию Монте-Карло, чтобы увидеть, насколько далеки от реальности, на самом деле...)