Collatz Conjecture Python-Salida incorrecta por encima de 2 billones(¡solo!)

python-3.x algorithm

Question

Escribí un guión básico en Python3 que calcula la conjetura de Collatz. Toma un entero positivo como entrada y devuelve el número de los pasos hasta que la secuencia desciende a 1.

Mi secuencia de comandos funciona perfectamente para cualquier entrada entera de menos de ~ 2 billones , pero por encima de este umbral, las salidas son demasiado pequeñas.

Como ejemplo, aquí hay algunas entradas, el resultado de mi script y el resultado correcto actual:

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 `

Los valores correctos de salida se basan en este enlace: http://www.ericr.nl/wondrous/delrecs.html

La salida de mi script es siempre exactamente 1,052 menos que la salida correcta para entradas superiores a 2 billones, pero no tengo idea de qué está causando esto.

¿Alguien puede explicar lo que está mal y cómo actualizar / corregir el script para que funcione correctamente para todas las entradas? Pensé que Python podía aceptar números arbitrariamente grandes sin ningún problema ...

¡Gracias!

# 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")

Answer 1

Esta línea:

n = int(n/2)

... convierte n en un flotador, lo divide en 2, luego lo convierte de nuevo en un int arrojando la parte fraccionaria.

Para enteros de hasta 2**52 , la conversión a flotante no tiene pérdida, pero para algo más grande, tiene que redondear al número de 53 bits más cercano, que pierde información.

Por supuesto, 2 trillones está muy por debajo de ese límite de 2**53 para la precisión de flotación, pero la secuencia de Collatz que comienza en N suele ser mucho, mucho más alta que N. No es del todo inverosímil que muchos números alrededor de 2 billones tengan secuencias que pasan 2**53 , mientras que muy pocos números debajo lo hacen. Incluso es posible que toda una larga secuencia de números que comienzan exactamente en 2 trillones pase de 2**53 pero no un solo número por debajo. Pero no tengo idea de cómo probar tal cosa sin construir toda la secuencia para cada número de hasta 2 billones. (Si hay una prueba, probablemente se apoyaría mucho en las pruebas parciales existentes de la conjetura bajo varias condiciones diferentes, que están por encima de mi retribución ...)

De todos modos, la solución es simple: quieres usar la división de enteros:

n = n // 2

Aquí hay un ejemplo para demostrar:

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

Para verificar que esto realmente está sucediendo en su código, intente esto:

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}'')

Cuando ejecuto esto:

$ 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

… me da:

           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

Por lo tanto, pasamos de 2**53 exactamente en los mismos casos en que obtuvimos la respuesta incorrecta.

Y para verificar la corrección, cambie el int(n/2) a 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

Entonces, ¿por qué siempre está apagado por la misma cantidad?

Bueno, eso es solo una coincidencia de los números específicos que estás usando.

Cuando pase 2**53 por 3n+1 , convertirá el último bit o los últimos 2 bits a 0, lo que significa que normalmente corta una gran parte de la cadena y la reemplaza con solo 1 o 2 divisiones Pero obviamente habrá algunos números donde la cadena a la que termina saltando es más larga que la correcta. De hecho, solo 3,743,559,068,799,123 3 intentos para encontrar uno: 3,743,559,068,799,123 debería tomar 326 pasos, pero se necesitan 370.

Sospecho (pero de nuevo, no me puedo imaginar cómo probarlo) que muchos números grandes van a terminar en el mismo rango alrededor de 375, un poco más cortos a medida que se hacen (logarítmicamente) más grandes. ¿Por qué? Bueno, hay tantos números que puedes redondear, y la mayoría de ellos probablemente estén en ciclos entre sí, comienzas a hacer una división truncada. Entonces, digamos que casi todos los números cerca de 2**53 tienen una longitud de ciclo de redondeo de un poco más de 50, y la mayoría de los números en el rango de billones alcanzan ese rango de 2**53 en un poco más de 300 pasos ... entonces la mayoría de ellos va a terminar alrededor de 375. (Esos números se sacaron de la nada, por supuesto, pero podrías hacer una simulación de Monte Carlo para ver qué tan lejos de la realidad son en realidad ...)