Coatz Conjecture Python - неправильный вывод выше 2 триллионов (только!)

Я написал базовый скрипт в Python3, который вычисляет гипотезу Collatz. Он принимает положительное целое число в качестве ввода и возвращает число шагов до тех пор, пока последовательность не упадет до 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

Выход моего скрипта всегда ровно на 1,052 меньше, чем правильный вывод для входов выше 2 трлн, но я понятия не имею, что это за причина.

Может ли кто-нибудь объяснить, что неправильно, и как обновить/исправить скрипт, чтобы он работал правильно для всех входов? Я думал, 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 not a valid entry. Please try again!\n")
    except ValueError:
        print("Sorry, that not a valid entry. Please try again!\n")

Ответ 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. (Конечно, эти цифры выведены из воздуха, но вы можете сделать симуляцию Монте-Карло, чтобы увидеть, насколько далеки от реальности, на самом деле...)