Capicúa con muchos saltos

propuesto por josejuan

Buscar el "número capicúa" (según la definición de Antonio Medina) más pequeño, tal que hagan falta más de 100 saltos para estabilizarlo (y quede estabilizado, no sirve el 196 que no estabiliza nunca).

Enunciado
Usando la definición de "número capicúa" del desafío propuesto por Antonio Medina:

DESAFÍO: encontrar el número N más pequeño, tal que para llegar al capicúa hagan falta más de 100 "saltos" (y quede estabilizado, no sirve el 196 que no estabiliza nunca).

NOTA: indicar el tiempo de computo total (y memoria) necesarios para obtenerlo SIN CONOCIMIENTO PREVIO (por ejemplo, no es válido dedicar una hora para obtenerlo y después acotar nuestro programa a buscar "cerca" de la solución).

Por ejemplo, del 80 al 90 es:
N     Saltos    Capicúa
============================
80    1         88
81    1         99
82    2         121
83    1         121
84    2         363
85    2         484
86    3         1111
87    4         4884
88    6         44044
89    24        8813200023188
90    1         99


Así, el número más pequeño para el cual hacen falta más de 20 saltos sería el 89 (pues no hay otro del 1 al 88 que tengan más de 20 saltos).

Ver todo el enunciado

Preguntas sobre el desafío
  • Por que el numero 88 tiene 0 saltos si se supone que hay que sumarlo con el invertido que es el mismo pero en ese caso no es capicúa el resultado de su suma por lo que hay que seguir sumando el invertido de ese numero, a mi me sale lo siguiente en el 88. (N= 80 1 saltos capicúa= 88) (N= 81 1 saltos capicúa= 99) (N= 82 2 saltos capicúa= 121) (N= 83 1 saltos capicúa= 121) (N= 84 2 saltos capicúa= 363) (N= 85 2 saltos capicúa= 484) (N= 86 3 saltos capicúa= 1111) (N= 87 4 saltos capicúa= 4884) (N= 88 6 saltos capicúa= 44044) (N= 89 24 saltos capicúa= 8813200023188) (N= 90 1 saltos capicúa= 99)

    En tu definición original no se indicaba *explícitamente* el caso de que el número inicial fuera capicúa. Aun cuando de la frase "Si se toma un numero cualquiera..." pueda implicar (implícitamente) que aun siendo capicúa se realiza la primera suma, yo tomé como definición lo contrario (simplemente porque a mí, ante la indefinición, me pareció más lógico, nada más). Así, en mi enunciado está definido sin ambigüedades (;P) por eso has preguntado. *AUN ASÍ* y dado que no hay soluciones, voy a cambiar el enunciado para que se ajuste a tu (ahora desambiguada) definición puesto que se me ocurrió el desafío a partir del tuyo ;)

Plantea tu pregunta

3 Soluciones

Dar mi solución

0votos
Capicúa con muchos saltos en C
por

josejuan

hace 4 años

La única optimización asintótica es eliminar del cálculo aquellos números cuyo recíproco es menor que él mismo. Por lo demás, mucho mejor usar aritmética decimal para no tener que convertir de base 2 a 10. En unos 10 minutos se obtiene que el número buscado es el 1.005.499.526 que genera el palíndromo 6633...3366

0votos
Capicúa con muchos saltos en Java
por

Mario Macías

hace 4 años

Versión MultiThreading de mi solución anterior. Además, me he tomado la licencia de asumir que si después de 1000 saltos no se ha encontrado un número Capicúa, es que no estabiliza. Después de 2 horas con los cuatro núcleos de mi i7, he llegado a encontrar varios números con 64 saltos, pero no más. Curiosamente todos daban el mismo número capicua resultante: 150296 64 682049569465550121055564965940286 151196 64 682049569465550121055564965940286 152096 64 68204956946555012105556496594028

0votos
Capicúa con muchos saltos en Java
por

Mario Macías

hace 4 años

Asumiendo que el único número que nunca estabiliza es el 196, el número que pides es 295. El número de saltos todavía no lo sé, puesto que se está calculando. El siguiente programa se puede ejecutar con el comando "java Capicua 100"

Dar mi solución