Computación

Números capicúa, que se ven al derecho y al revés igual

. Hay una vieja conjetura que data de los años 30s del siglo pasado que indica el procedimiento: Tómese un número entero positivo. Este se escribe en orden inverso y ambos números se suman.
domingo, 25 de septiembre de 2022 · 17:23

CIUDAD DE MÉXICO (proceso.com.mx).-Los números son fascinantes y las matemáticas es uno de esos temas que han absorbido las neuronas de las personas más brillantes en la ciencia. los números pueden exhibir ciertas propiedades, por ejemplo, la de la simetría bilateral. A esto se le llaman números palíndromos o capicúa (del catalán, cabeza y cola). Definimos estos como aquellos números que se leen igual de izquierda a derecha que derecha a izquierda. Ejemplos: 161, 2992, 3003, 2882[1].

Hay interesantes ejemplos de números palindrómicos, por ejemplo, el 1881, que fue un año capicúa y que, además, puede leerse invertido (como si estuviese en un espejo, sin cambiar su valor). El número 1961 es invertible, pero no es palindrómico. El siguiente año palindrómico fue 1991, a todo esto y 2002 podría considerarse también capicúa evidentemente.

Una pregunta que surge es si es posible generar números palindrómicos y aparentemente sí. Hay una vieja conjetura que data de los años 30s del siglo pasado que indica el procedimiento: Tómese un número entero positivo. Este se escribe en orden inverso y ambos números se suman. El proceso se repite con el número sumado y se continúa con este procedimiento hasta que se tiene un número capicúa. La conjetura afirma que tras un número de pasos finito de sumas, se obtendrá un capicúa.

Por ejemplo, si tomamos el número 73 tendremos:

73 + 37 = 110

110 + 011 = 121 que es un número capicúa como queríamos.

Para los números del 1 al 9 la conjetura es trivial: por ejemplo, si tomamos el 5, tenemos:

5 + 5 = 10

10 + 01 = 11 lo cual es capicúa.

Para los números de dos dígitos, si sus cifran suman menos de 100, entonces se obtendrá en el primer paso un número palindrómico. Por ejemplo, 35 + 53 = 88. También se sabe que si las cifras suman 10, 11, 12, 13, 14, 15, 16 o 18, se obtienen palíndromos tras 2, 1, 2, 2, 3, 4, 6, y 6 pasos, respectivamente. Cabe decir que los números de dos dígitos cuyas cifras sumen 17 son la excepción y solamente el 89 (y su retrógrado 98) cumplen con la condición mencionada. Con cualquiera de esos números no se logran los capicúas hasta llegar a la iteración 24:

89 + 98 = 187

187 + 781 = 968

968 + 869 = 1837

1837 + 7381 = 9218

9218 + 8129 = 17347

17347 + 74371 = 91718

91718 + 81719 = 173437

173437 + 734371 = 907808

907808 + 808709 = 1716517

1716517 + 7156171 = 8872688

8872688 + 8862788 = 17735476

17735476 + 67453771 = 85189247

85189247 + 74298158 = 159487405

159487405 + 504784951 = 664272356

664272356 + 653272466 = 1317544822

1317544822 + 2284457131 = 3602001953

3602001953 + 3591002063 = 7193004016

7193004016 + 6104003917 = 13297007933

13297007933 + 33970079231 = 47267087164

47267087164 + 46178076274 = 93445163438

93445163438 + 83436154439 = 176881317877

176881317877 + 778713188671 = 955594506548

955594506548 + 845605495559 = 1801200002107

1801200002107 + 7012000021081 = 8813200023188

Martin Gardner, uno de los divulgadores de las matemáticas más populares, indica que en 1967 Charles W. Trigg, un matemático de California, descubrió que entre los enteros menores a 10,000 había 249 números que no generaban capicúas aún después de ejecutar 100 iteraciones[2]. El menor de esos números es el 196, que consideraremos más adelante. Harry Sal, en 1975, realizó en el Centro Científico de Israel 237,310 iteraciones del número 196 y no halló ningún resultado palindrómico. Se sospecha desde entonces que la conjetura es falsa[3], aunque sigue siendo indecidible el caso del 196.

Hay que indicar que fuera de las 249 excepciones (sobre los 10 mil primeros enteros), todos producen capicúas en no más de 24 iteraciones y solamente el 89 (y el 98, desde luego), requieren las 24. De los capicúas generados, el mayor es 16,668,488,486,661, el cual se genera a partir del 6999 (y su retrógrado, el 9996) o por el 7998 (y su retrógrado, el 8997), en 20 pasos.

Pero aún en esta era de la computación masiva, no se ha hallado que la conjetura mencionada 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 de ellos no llevan a ningún palíndromo o capicúa. 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[4].

En abril de 1984 apareció en la columna de Scientific American,“Computer Recreations”, un artículo sobre estos patrones matemáticos[5] y los esfuerzos para probar la conjetura han sido extraordinarios. Por ejemplo, John Walker[6] 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.

(Punto de detención en la iteración 2415836)

(El número contiene 1000000 de dígitos)

Así entonces, el número 196 había crecido hasta un millón de cifras sin que fuese palindrómico[7].

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[8].

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[9].

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 inició 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)[10]. Sin embargo, eventualmente Doucette llegó a más de 13 millones de cifras y ahí decidió detenerse aparentemente[11]. 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[12]:

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[13].

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?

[1]https://es.wikipedia.org/wiki/Capic%C3%BAa

[2] C.W. Trigg, Palindromes in addition, Mathematics Magazine, 40 (1967) 26-28

[3] Martin Gardner, Circo Matemático, Alianza Editorial, 1985

[4] Yutaka Nishiyama, Numerical Palindromes and the 196 Problem, International Journal of Pure and Applied Mathematics, Volume 80 No. 3 2012, 375-384 (http://www.ijpam.eu ijpam.eu)

[5] F. Gruenberger, Computer Recreations, How to Handle Numbers with Thousands of Digits, and Why One Might Want To., Scientific American, 250 [No. 4, April, 1984], 19-26

[6]http://www.fourmilab.ch/documents/threeyears/threeyears.html

[7]El millón de cifras puede descargarse de http://www.fourmilab.ch/documents/threeyears/checkpoints/196.ck2415836.gz

[8]Los dos millones de cifras pueden descargarse de este sitio: http://www.fourmilab.ch/documents/threeyears/checkpoints/196.ck4830868.gz

[9]http://www.fourmilab.ch/documents/threeyears/two_months_more.html

[10] Hoy las computadoras caseras corren a 3.5 GHz, diez veces más rápido que la máquina usada por Doucette.

[11]http://jasondoucette.com/worldrecords.html

[12]http://jasondoucette.com/worldrecords.html#196

[13]http://www.p196.org/

Comentarios