Números de Lychrel, Algoritmo196 y Project Euler 55

Uno de los problemas abiertos de Teoría de Números es encontrar números de Lychrel. Estos números hipotéticos desafían el llamado algoritmo196, -una secuencia que utiliza el viejo truco de sumar y agregar para obtener números palíndromos o capicúas. El algoritmo196 toma cualquier número natural, invierte sus dígitos y le suma el original; a nuestro interés, si la suma no es capicúa repite el proceso a partir de dicha suma, por ejemplo

338 + 833 = 1171
1171 + 1711 = 2882

Los números de Lychrel son entonces, los que no producen capicúas al aplicar el algoritmo196. De nuevo, esto es un problema abierto, y precisamente 196 es el primer número de Lychrel que se ha conjeturado. Consulta La conjetura del 196 en Gaussianos. En seguida muestro una parte del problema 55 de Project Euler y mi solución, que es vulgar y silvestre lógica potenciada con el lenguaje Python, en realidad no hice un análisis más allá.

[…] Aunque nadie lo ha demostrado aún, se cree que algunos números, como el 196, nunca producen un capicúa. Un número que nunca forma un capicúa mediante el proceso de sumarse a sí mismo invertido se denomina un número de Lychrel. Debido a la naturaleza teórica de estos números, y para el propósito de este problema, vamos a suponer que un número es Lychrel hasta que se demuestre lo contrario. Además, se te da la información de que cada número inferior a diez mil, (i) será un capicúa en menos de 50 iteraciones, o, (ii) nadie, con toda la potencia de cálculo que existe, ha logrado por ahora asociarlo a un capicúa.

De hecho, 10677 es el primer número que requiere más de cincuenta iteraciones antes de producir el capicúa: 4668731596684224866951378664 (53 iteraciones, 28 dígitos).

Sorprendentemente, existen números capicúa que son a su vez números de Lychrel; el primer ejemplo es 4994.

¿Cuántos números de Lychrel hay inferiores a diez mil?

Solución en Python:

import time

t0 = time.time()
L, M = 0, 10000
for i in range(1,M):
    s = str(i+int(str(i)[::-1]))
    lychrel = True
    j = 1
    while j <= 50:
        if s == s[::-1]:
            lychrel = False
            break
        j += 1
        s = str(int(s)+int(s[::-1]))
    if lychrel == True:
        L += 1
print 'Hay',L,'números Lychrel inferiores a',M
print 'Tiempo de cómputo:',time.time()-t0,'segundos'

Hay 249 números Lychrel inferiores a 10000
Tiempo de cómputo: 0.345999956131 segundos

Como he dicho, la solución no son en realidad números de Lychrel, y asimismo el encontrarlos o negarlos quizás dependa más de una astuta demostración que de potentísimos ordenadores.