Un nuevo reto de la programación lúdica: Sabemos que el número 196 no se ha podido demostrar que es palindrómico. Hállese la mayor cantidad de iteraciones y el mayor número al que se pueda llegar sin que el programa falle. Ése es el reto.
Aún en esta era de la computación masiva, no se ha hallado que la conjetura sobre los números capicúas, que fue
el reto de programación lúdica pasado, funcione para el número 196, la cual sigue siendo un problema matemático sin resolver. Se sabe que los números, entre el 100 a 999, 13 no llevan a ningún palíndromo. Estos son: 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986. El 196 es el primero de ellos y evidentemente su retrógrado el 691 tampoco llega a ser capicúa.
Podemos entonces considerar dos grupos, el primero, conteniendo 196, 295, 394, 493, 592, 689, 691, 788, 790, 887 y el 986, y un segundo grupo compuesto por el 879 y el 978. A los números 196 y 879 se les llama “números generadores” o “semillas”. La razón de esto es que el 691 es el retrógrado del 196 por lo que son parte del mismo grupo: 196 + 691 = 691 + 196 = 887. El número 295 y el 592 llevan al mismo número, 887, después de una primera iteración, por lo que se consideran parte del mismo grupo.
En abril de 1984 apareció en la columna de
Scientific American “Computer Recreations”, un artículo sobre estos patrones matemáticos y los esfuerzos para probar la conjetura han sido extraordinarios. Por ejemplo, John Walker indica que el 12 de agosto de 1987 puso su estación de trabajo Sun 3/260 para tratar de resolver si el 196 era un número palindrómico. El programa tenía algunos controles, que se guardaban en un archivo cada dos horas y en caso necesario el sistema reiniciaba la tarea desde los últimos datos hallados en dicho archivo. Así, si algo fallaba (por ejemplo, se cortaba la energía eléctrica), podía reanudarse el proceso sin problemas. Entonces el programa corría día y noche sin intervención humana.
Dice Walker que finalmente, casi cuando se cumplían tres años de ejecución ininterrumpida del software, cinco minutos antes de la media noche, el programa mandó el siguiente mensaje:
Stop point reached on pass 2415836.
Number contains 1000000 digits.
(El número contiene 1000000 de dígitos)
(Punto de detención en la iteración 2415836)
Así entonces, el número 196 había crecido hasta un millón de cifras sin que fuese palindrómico.
Esto podría quizás considerarse el final de la historia, pero sorpresivamente en 1995, Tim Irvin retomó el trabajo de Walker usando una supercomputadora, empezando en el número de un millón de cifras y cuando el sistema llegó a un número con dos millones de cifras, encontró también que no había sido localizado ningún número palindrómico.
Irvin inició su búsqueda el 5 de julio de 1995 y después de una semana de pruebas y corrección de errores, el programa trabajó casi ininterrumpidamente, a excepción de las horas de respaldo diario del sistema. En la mañana del 22 de agosto de ese mismo año, el programa se detuvo en los dos millones de cifras, de nuevo, sin encontrar el ansiado número capicúa.
Irvin terminó su búsqueda y aunque ha jugado con la idea de seguirla, considerando que el sistema de súper cómputo se ha renovado, parece decidido a no continuar por diversas razones. Por una parte, el tiempo de súper cómputo no es barato y por otra parte, hay muchos problemas más importantes que atacar que el resolver la conjetura. No obstante esto, Irvin pone a la disposición el programa y los controles para que el sistema se detenga cuando se llegue a 3 millones de cifras.
Pero Jason Doucette, en 1999 decidió retomar el trabajo de Irvin y usando una computadora casera, entró a esta gran búsqueda. En este caso, el programador desarrolló software en ensamblador (buscando optimizar los recursos), y en 1999, el 9 de agosto, se inicio la ejecución del software, en una máquina Pentium II, a 266 Mhz. El sistema alcanzó la marca de un millón de cifras en 1 día y 18 horas, lo cual es notable si consideramos que Walker tardó 3 años casi en llegar a esa cantidad de cifras. 5 días y 10 horas después, Doucette llegó a la marca de los 2 millones de cifras. Se compararon los resultados y no se hallaron divergencias, por lo que se asume que el software no tiene errores.
La marca de los tres millones de cifras se alcanzó 8 días y 7 horas después. Desde luego, mientras mayor es el número más sumas tendrá que hacer. 13 días y 8 horas después se alcanzó la cifra de 5 millones de dígitos. Al llegar a este resultado, Doucette cambio de hardware y el programa reinició su búsqueda en una máquina Celeron, con un procesador de 400 Mhz (lejos, muy lejos, del estándar actual).
Eventualmente Doucette llegó a más de 13 millones de cifras y ahí decidió detenerse aparentemente . Sin embargo, Ian Peter logró la cifra de 10 millones de dígitos en poco más de cinco horas. Esto lo hizo en una máquina de 500 Mhz Athlon.
El trabajo de Ian Peter es además interesante porque encontró algunos números palindrómicos que tardan más que las 24 iteraciones que la mayoría de los números necesita. En la siguiente tabla se observan estos números palindrómicos, con sus respectivas iteraciones y el palíndroma generado:
Finalmente Wade van Landingham entró a la búsqueda y a partir de casi 14 millones de cifras de Doucette, llegó a un número de 300 millones de dígitos, lo cual son casi 725 millones de iteraciones y de nuevo, parece no encontrarse el capicúa que se inicia con 196. Sin embargo, hay que hacer énfasis en que hasta el momento lo único que podemos concluir es que no se sabe si el 196 es número palindrómico. Esto sigue siendo indecidible .
El hecho de que no todos los números sean capicúas podría hacernos pensar que existe una asimetría en la conjetura, aunque en términos reales, no es el único número que no cumple con ello. Los matemáticos se preguntan, sin embargo, ¿Qué tiene de especial el número 196?
Todo lo anterior es simplemente el preludio del nuevo reto de programación lúdica. Se trata de procesar el número 196 para ver si es palindrómico (lo cual no sabemos a pesar de que se han hecho millones de iteraciones) y entregar el número más grande al que el programa del concursante pueda llegar. Por ejemplo, si pusiésemos a trabajar el 89 y llegásemos a la iteración 24 que da 8813200023188, éste sería el valor más grande que podríamos encontrar del número con el que partimos. Pero en el caso del 196 no parece haber un límite de iteraciones y de lo que se trata es que el concursante entregue el mayor número con la mayor cantidad de iteraciones.
Cabe señalar que si hay más de un programa que llega al máximo valor, ganará quien lo haya enviado primero. El resultado es inapelable.
Al ganador (si es de la Ciudad de México), le daré una taza con el logotipo de la Morsa. Si es de otro país o de provincia, le mandaré un USB de al menos 8 GB. La razón de esto es que mandar una taza por mensajería es estúpidamente caro.
Las soluciones me las pueden mandar a
morsa@la-morsa.com.
Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas que den el mismo tiempo al procesar la lista de 10 mil números, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto.
En este caso no hay restricción en qué lenguaje usar. El concursante tiene que mandar su código fuente, el ejecutable (si aplica) y los resultados obtenidos. El concurso tendrá una vigencia de unas tres semanas, aproximadamente. Así que manos a la obra, digo, dedos al teclado…
Ps. El concurso anterior (sobre la conjetura palindrómica) se ha cerrado y en unos días pondré quién fue el ganador. Estén atentos.
