martes, 5 de mayo de 2009

El número de los 300 millones de dígitos

Un número palindrómico (o capicúa) es un número natural que es el mismo cuando es escrito de izquierda a derecha o de derecha a izquierda. Por ejemplo: 1, 2, 3 ..., 9, 11, 22 ..., 99, 101, 111, 121 ..., 191, ... 100040001, etc. Estos números están escritos en base 10, pero en general, se puede tomar un número de cualquier base que cumpla con estas características (una web con cosas curiosas sobre estos números es http://www.geocities.com/~harveyh/palindromes.htm).

Se puede convertir un número no palindrómico en un número palindrómico por medio de un par de operaciones sencillas: 1. Se invierte el número que no es palindrómico. 2. Se suma el número invertido al número que no era palindrómico. 3. Se repite el proceso con el número obtenido como resultado hasta que el número obtenido sea palindrómico. Por ejemplo, tomemos el número 132: 1. Lo invertimos: 231. 2. Lo sumamos a su inversa: 132+231=363. 3. El número obtenido es palindrómico; entonces, hemos obtenido lo que queríamos. Si no fuese así, continuamos invirtiendo el número y sumándolo con su inversa. Por ejemplo, tomemos el número 87:

87 + 78 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884

4884 es palindrómico.

El número 89 es especialmente demorón entre los primeros 100 números naturales, necesitando 24 iteraciones para llegar a ser palindrómico:


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

Este procedimiento para convertir números que no son palindrómicos en números que sí lo son se llama algorimo 196.

Un número de Lychrel es, por otro lado, un número que no se puede convertir en palindrómico por medio de esta operación. Existe una conjetura, llamada Conjetura de los Números Palindrómicos, que dice que todos los números naturales no palindrómicos llegarán eventualmente a convertirse eventualmente en palindrómicos por medio del algoritmo 196 (luego veremos el porqué de este nombre). O, en otras palabras, que no existen números de Lychrel. Hasta ahora, no ha logrado ser probada falsa, no de manera analítica, salvo para los números de base 2, los llamados números binarios, con los que trabajan las computadoras. Heiko Harborth demostró la falsedad en base 2 en 1977. En otras bases, se ha probado que ciertos números vuelven a ser los mismos luego de aplicar el proceso, y por tanto, no cumplen la conjetura

Pero se cree que la conjetura es falsa también para los números de base 10. Esta creencia se sustenta no en un método analítico, sino en que se está probando cada número a la "fuerza bruta", es decir, usando una computadora y aplicando el algoritmo 196 a cada número, y de esta forma se ha encontrado números que hasta ahora no pueden ser convertidos en palindrómicos. Específicamente, entre los primeros 100 mil números naturales se han encontrado 5996 que aparentemente nunca genererán un número palindrómico. El primero de ellos es el 196, y le siguen, por nombrar algunos, 887, 1675, 7436...

El 196 ha sido el más estudiado de los números que aparentemente son números de Lychrel, por ser el menor de todos. Desde que se inventaron las computadoras se comenzaron los cálculos. En 1972, Paul Leyland hizo 50 mil inversiones y sumas con el número 196, y obtuvo un número de 26 mil dígitos que no era palíndromo todavía. En 1975, Harry J. Saal, del Centro Científico de Israel, hizo 237 310 sumas con el mencionado número 196, sin llegar a obtener un palíndromo de él. En 1990, luego de poner a su computadora a calcular por tres años, John Walker recibió cinco minutos antes de la medianoche del 24 de mayo un mensaje impreso por ella: Stop point reached on pass 2 415 836. Number contains 1 000 000 digits. Luego de que Walker obtuviera 1 millón de dígitos a partir del proceso de suma e inversión con el número 196, y no llegase a conseguir un número palindrómico que pusiera fin a su búsqueda, las búsquedas de varios programadores y matemáticos han ido en aumento, ayudadas por la mayor potencia de cálculo de las nuevas computadoras.

Jason Doucette llegó a los 13 millones de dígitos en junio del 2000. Istvan Bozsik llegó a los 29 millones dos años después, en marzo. En setiembre de ese mismo año, Ben Despress llegó a los 45 millones. En diciembre, Eric Sellers obtuvo 66 millones. En febrero del 2006, Eric Goldstein sumó e invirtió un número de 293 millones de cifras, sin conseguir que 196 se convirtiese en un número palindrómico.

Para tener una idea de qué tan grandes son los números que genera este proceso, el número 196 luego de 200 iteraciones se transforma en:
9104495467417656552982698022556296323012072552812103235826563197972803556567037646054008

El programa que hizo Jason Doucette puede hacer este cálculo enorme en tan poco como... ¡0.6 milésimas de segundo!. El cálculo completo, para llegar a los 13 millones de dígitos, le tomó 32 millones de iteraciones y 283 días de cálculo computacional. Una persona haciendo 3 de estas sumas por segundo demoraría ¡3.3 millones de años en terminar el cálculo!

Wade VanLandingham llegó el 1 de mayo del 2006 a los 300 millones de cifras sin conseguir probar que el número 196 no sea un número Lychrel. Un esfuerzo inútil ante todo punto de vista económico, pero asombroso.

No hay comentarios:

Publicar un comentario en la entrada