Pruebe la conjetura de Collatz
523Más información http://www.unocero.com
Hay una insólita clase de problemas aritméticos los cuales pueden ser asociados a un problema computacional de iteraciones, "loops" o "bucles". La idea es generar una serie de enteros de acuerdo a cierta regla. Se pregunta entonces uno, si la serie acabará entrando en uno o más bucles, en los que un conjunto de enteros se va repitiendo periódicamente. Y aunque esto suene difícil de comprender, veámoslo con la "conjetura de Collatz": Tómese algún número entero positivo. Divídase entre dos si es par; si es impar, multiplíquese por tres y sumémosle uno al producto. Si aplicamos este procedimiento repetidamente, eventualmente llegaremos a uno. Si esto ocurre, diremos que el número inicial con el que empezamos la secuencia es maravilloso.
La pregunta fundamental de esta conjetura es la siguiente: Dado cualquier número entero positivo y utilizando el procedimiento descrito, ¿se caerá en a secuencia cíclica 2,1,4,2,1,4,...? Nadie hasta ahora ha podido demostrar que esto ocurra forzosamente. Nadie ha podido, sin embargo, hallar un contraejemplo.
A este problema se le denomina también el problema 3x + 1, el cual se resiste a los esfuerzos por resolverlo. Según Richard guy, fue propuesto antes de la Segunda Guerra Mundial por Lothar Collatz, hoy matemático de la Universidad de Hamburgo (*), cuando era estudiante. En una conferencia que dio en 1970, H.S.M Coxeter ofreció 50 dólares por una demostración que él pudiera entender y 100 dólares por un contraejemplo. Tal fue el diluvio de falsas demostraciones que Coxeter no está ya dispuesto a evaluarlas. Parece, en efecto, que es tan fácil cometer sutiles errores en las demostraciones de este tipo como en las del último teorema de Fermat (que a todo esto, ya ha sido demostrado, según entiendo). De hecho, Paul Erdös, en 1982, expresó su opinión (¿y cuál más calificada que la suya?), de que si la conjetura es verdadera, la teoría de números carece hoy de instrumental para demostrarla.
Un grupo de investigadores del laboratorio de inteligencia artificial del MIT ha puesto a prueba, mediante computadora, todos los enteros positivos hasta el 60,000,000, sin encontrar una sola excepción. Se descubrió además que si la regla 3n + 1 utilizada cuando es impar se reemplaza por 3n - 1, el resultado, en valores absolutos, es el mismo que si se comenzase con un número entero negativo y se siguiera la antigua regla. En este caso se descubrió que todos los enteros negativos hasta -100,000,000 caían en uno de estos tres bucles:
2,1,2,...
5,14,7,20,10,5,...
17,50,25,74,37,110,55,164,82,41,122 61,182,91,272,136,68,34,17,...
Michael Beemer, William Gosper y Rich Schroeppel dan estor resultados en HACKMEM (abreviatura de Hacker Memo), #239, MIT 1972.
Parece que a nadie se le ha ocurrido una feliz idea que permita establecer el caso general para todos los enteros no nulos (el cero pertenece, evidentemente, al bucle 0,0,0,...). Nadie sabe tampoco si hay enteros que generen sucesiones divergentes hacia infinito carentes de bucle.
Al poco tiempo de empezar este juego, se descubrió que no era preciso ensayar los números pares, ni tampoco los impares de la forma 4k + 1, 16k + 3 o 128k + 1. De este modo, los programas de computadora se abrevian mucho. Evidentemente, tan pronto como una sucesión tropieza con una potencia de 2, muchas veces, tras una serie caótica de altibajos, se desploma vertiginosamente hacia 4,2,1. La potenbcia de 2 hacia la que más sucesiones convergen es 16.
Entre los números menores de 50, el de peor comportamiento es el 27. Tras 77 pasos alcanza una cima de 9232. Bastan después 34 pasos para reducirlo a 1. Cuando el matemático John H. Conway presenta en sus lecciones la conjetura 3x + 1, le gusta ir a la pizarra y decir: "tomemos un número al azar, el 27 por ejemplo, y veamos qué sucede".
La conjetura de Collatz es computacionalmente irreductible aparentemente, lo cual significa, en otras palabras, que sólo mediante la ejecución explícita para cada número, es posible ver si el número en cuestión es maravilloso o no. Lo que equivaldría a decir que no puede existir una demostración analítica del problema en cuestión.
Retemos al lector de unocero: hágase un programa que pruebe la conjetura de Collatz para cualquier cantidad de cifras (es decir, que use precisión matemática infinita). Los dos primeros resultados correctos recibirán la colección de cuatro libritos (tres de sudoku y uno de ajedrez), de mi autoría. Si quieren ver mi propio software que hace este trabajo, escríbanme a morsa@la-morsa.com y se los mandaré a vuelta de correo.