in

Collatz: el programa más simple que no comprende del todo

1chzeIszudlOkUVyRZQp74w

Collatz: el programa más simple que no comprende del todo

Una exploración computacional con Wolfram Language

Arnoud Buzing

2 de oct de 2020·4 min de lectura

1*chzeIszudlOkUVyRZQp74w

Me gusta pensar que lo sé todo, especialmente cuando se trata de programación. Y, durante mucho tiempo, pensé que si miraba un fragmento de código el tiempo suficiente, podría comprender completamente su comportamiento. Simplemente lea el código, línea por línea, y piense en los posibles casos de declaraciones if y bucles for. Con suficiente tiempo y paciencia, todo el código es completamente comprensible.

Y, sin embargo, escribí un código que not corre como se esperaba. De hecho, esto pasó mucho. La mayoría de las veces, nueve de mis primeros diez intentos de escribir un nuevo código son experiencias en la codificación de la humildad. Pero aún así, atribuí esto a errores de tipeo, a escribir fragmentos de código incompletos y tal vez a la impaciencia y a no pensar bien las cosas antes de ingresar el código real.

Todo eso cambió un día cuando alguien me mostró un fragmento de código de Wolfram Language que implementaba el algoritmo Collatz. La idea es muy simple: escribe una función que acepte un número entero positivo como único argumento. Si el número es 1, ha terminado y devuelve 1 de la función. Si el número es mayor que uno, hay dos ramas: si el número es par, divide por dos y devuelve ese número. Si el número es impar, devuelve tres veces ese número más 1.

collatz[1] = 1
collatz[n_Integer /; n>1 ] := If[ EvenQ[n], n/2, 3n+1 ]

Hasta aquí todo bien. Puedes probar esto con diferentes enteros y todo es perfecto:

collatz[5] --> 16
collatz[8] --> 4

Pero la bola curva llega cuando escribes un programa que calcula la siguiente secuencia:

collatz[16] --> 8
collatz[8] --> 4
collatz[4] --> 2
collatz[1] --> 1 (* done! *)

Una forma sencilla de implementar esto en Wolfram Language es con NestWhileList:

collatzSequence[n_Integer /; n > 0] := 
NestWhileList[collatz, n, # != 1 &]

Un caso de ejemplo con n = 16 da:

collatzSequence[16] --> {16, 8, 4, 2, 1}

Todo eso parece bastante simple, pero hay un pequeño problema persistente: en el momento en que te encuentres con un número impar, el siguiente número será tres veces (más uno) más grande. Ese siguiente número también será par, lo que significa que el número siguiente se reducirá a la mitad nuevamente. Aquí tienes un ejemplo, cuando comienzas con un número impar:

collatzSequence[17] --> {17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}

La secuencia de números primero sube a 52, pero luego se colapsa rápidamente de nuevo a 1. Claramente, esto sucederá para todos los números, ¿eventualmente? Desafortunadamente, tenemos que considerar la posibilidad de que haya números que produzcan secuencias que reboten para siempre y nunca lleguen a 1. Por ejemplo, podría haber una secuencia en la que los números reboten lentamente y se hagan cada vez más grandes con el tiempo. Leer el código no ayuda mucho aquí. A continuación, se muestra un ejemplo de un número inicial en el que la secuencia no llega rápidamente al 1:

collatzSequence[63728127]
1*MWbhRfgAj1Gi52 cAmApqw

Aquí hay un diagrama de esta secuencia de números:

1*97qBGTQqcmyw9TM3B5m0VQ

A pesar de que podemos leer el código y comprender lo que sucede en cada paso del camino para cualquier número, no podemos saber si el programa termina alguna vez (o incluso saber la longitud de la secuencia para un número dado). Las personas que han examinado este problema en profundidad han conjeturado (pero no probado) que cada número tiene una secuencia que termina en 1. Esta conjetura se llama la Conjetura de Collatz en honor a Lothar Collatz, quien fue el primero en plantear este problema.

La gente ha hecho muchos descubrimientos y visualizaciones interesantes para este problema sin resolver realmente la conjetura en sí. Una visualización muy interesante es una trama de muchos puntos de partida y cómo estas secuencias finalmente se encuentran y se fusionan entre sí:

1*DeV3cHsWjIgq2tAjagBIUw

O un gráfico más simple que muestra cómo varias secuencias de Collatz se fusionan y finalmente se encuentran en el número 1:

La lección que aprendí fue que no siempre es posible comprender incluso los programas más simples. Como resultado, tampoco me siento tan mal cuando miro un archivo de código fuente enormemente grande que estaba mal documentado. En muchos casos, lo mejor que puede hacer es ejecutar un programa con muchas entradas diferentes para desarrollar intuiciones y conjeturas y usar eso para iterar su código hasta un punto en el que se comporte principalmente como lo esperaría. Quizás algún día alguien encuentre un número inicial para la secuencia de Collatz que no termine en cero. ¡Pero creo que este es el tipo de rompecabezas de programación que quizás nunca se resuelva!

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

toma foto

¿Por qué tiembla la cámara trasera de mi iPhone y cómo puedo solucionarlo?

Archivo JavaFX Scene Builder 1.x