Números automórficos- parte 3

Este post es la tercera parte del problema propuesto en este otro post sobre números cuyo cuadrado termina con el propio número, como 25 (porque 25² = 625, que termina de nuevo en 25). Aquí veremos un resultado matemático que nos ayudará a refinar nuestro algoritmo.

Recordemos que habíamos probado un algoritmo de fuerza bruta, es decir, uno en el que se probaba todos los números posibles y que era demasiado lento. A pesar de que no era el mejor método, conseguimos obtener unos cuantos números. Por ejemplo, para longitud 7 o menor, estos son todos los números automórficos que existen:

1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, 2890625, 7109376

Vemos que, con excepción del 1, todos los demás acaban en 5 o en 6. ¿Será que no hay ningún número automórfico que termine de otra forma? Nuestra observación no es determinante, pues únicamente tenemos una pequeña muestra de números. A priori, podría existir un número de 39 cifras que acabe en 4 y que sea automórfico.

Si nos fijamos bien, los números de nuestra lista no sólo terminan en 5 o en 6, sino que siempre acaban en 25 o en 76 (exceptuando los propios 5 y 6, claro). Y no sólo eso, sino que a partir de cierto punto todos terminan en 376 o en 625; y, más tarde, en 9376 o en 90625. ¿Ves el patrón?

Cada número de esta lista se ha construido a partir de uno anterior que también es automórfico, añadiendo un dígito al principio. Por ejemplo, 7109376 termina en 109376, que también aparece en nuestra lista. A su vez, si quitamos otro dígito, 09376 (o, lo que es lo mismo, 9376) también es uno de nuestros números. Y así podríamos continuar hasta quedarnos con un único digito, el 6. Parece que se repite demasiado para ser una casualidad, ¿verdad?

Esto invita a pensar que para cualquier número automórfico, si lo partimos por cualquier sitio y nos quedamos con la parte de la derecha (el final), también es automórfico. Por ejemplo, partimos 2890625 y nos quedamos con 90625. Efectivamente, también es automórfico.

A continuación, veremos un boceto de la demostración de este resultado. Para ello, utilizaré la notación y¯x para referirme a la concatenación de los números y y x. Por ejemplo, 12¯345 = 12345.

Teorema: sean x e y dos números de m y n cifras, respectivamente, tales que y¯x es un número automórfico. Entonces, x también es automórfico.

Demostración: que y¯x sea automórfico significa que su cuadrado termina con y¯x, es decir, que (y¯x)² = A¯y¯x, para algún número A. Tenemos que probar que x² = B¯x, para algún B.

Por la definición de concatenación, y dado que x tiene m cifras, y¯x es lo mismo que y*10^m + x. Si calculamos su cuadrado, (y¯x)² = y²*10^2m + 2xy*10^m + x². Usando esta ecuación y el hecho de que y¯x es automórfico, tenemos la siguiente igualdad: y²*10^2m + 2xy*10^m + x² = A*10^m+n + y*10^m + x.

En esa ecuación, para las últimas m cifras, los términos y²*10^2m, 2xy*10^m, A*10^m+n e y*10^m no afectan en nada. Así que, si simplificamos módulo 10^m la ecuación de arriba:

x² ≡ x (mod 10^m)

O, lo que es lo mismo, existe algún número B tal que x² = B*10^m + x. Es decir, x² = B¯x. Por lo tanto, x es automórfico. QED

Una vez que hemos demostrado este importante teorema, el siguiente corolario resulta trivial:

Corolario: sea x un número NO automórfico. Entonces, a¯x tampoco es automórfico, para cualquier dígito a.

Demostración: supongamos, por el contrario, que a¯x fuese automórfico. Por el teorema anterior, cuando y = a, tenemos que x es automórfico, lo cual es una contradicción. Así, a¯x no es automórfico. QED

¿Qué quiere decir este corolario? Muy sencillo: si encontramos un número que no es automórfico, como 4, cualquier otro que acabe por este número, como 24, tampoco es automórfico. Rápidamente podemos ver que 64725 no es automórfico, ya que 725 no lo es.

Usando este resultado, ¿sabrías encontrar ahora una forma más eficiente de calcular todos los números automórficos que la del post de ayer? ¡No te pierdas el siguiente post!