Números automórficos- parte 4

Éste es el cuarto y último post relativo a los números automórficos, cuyo cuadrado termina con el propio número, como 25 (porque 25² = 625, que termina de nuevo en 25). ¡Por fin encontraremos todos los números automórficos de 15 cifras o menos!

Después de haber probado un algoritmo poco eficaz, vimos algunos patrones que se generaban en la lista que íbamos obteniendo y demostramos un importante resultado:

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

Sabemos que 8 no es automórfico, por lo que tampoco lo será 18, ni 628, ni 7145168. De hecho, conocemos muchísimos números que no son automórficos. ¿Por qué deberíamos ir comprobando cada número como en nuestro anterior algoritmo, cuando podemos saltárnoslos?

Sea {x₁, x₂,..., x_n} la lista de todos los números automórficos de m cifras o menos. Si tiene menos de m cifras, le añadimos al principio tantos 0's como sea necesario (por ejemplo, 00376 tiene 5 cifras). Entonces, TODOS los números automórficos de exactamente m+1 cifras están incluidos (junto con otros muchos que no lo son) en la lista:

{1¯x₁, 2¯x₁,..., 9¯x₁, 1¯x₂,..., 9¯x_n}

Es decir, en total hay 9*n candidatos. ¡Muchísimos menos de los que teníamos antes! Este algoritmo seguro que es más rápido.

Veamos un ejemplo: tenemos la lista de los números automórficos de 4 cifras o menos, que es {0001, 0005, 0006, 0025, 0076, 0376, 0625, 9376}. Según lo de arriba, para encontrar los de 5 cifras, los únicos candidatos que deberíamos mirar son {10001, 20001, 30001,..., 90001, 10005, 20005,..., 90005, 10006, 20006,..., 90006, 10025, 20025,..., 90025, 10076, 20076,..., 90076, 10376, 20376,..., 90376, 10625, 20625,..., 90625, 19376, 29376,..., 99376}, que son 9*8 = 72 posibilidades (frente a las 90000 que teníamos que comprobar en el algoritmo de fuerza bruta). La mayoría de ellas no cumplen la condición de automorfismo, así que las descartamos tras unos cálculos y nos quedamos únicamente con 90625, que es el único número automórfico de 5 cifras.

Ahora que ya conocemos este algoritmo, el problema se vuelve más sencillo. De la lista de números automórficos de hasta 8 cifras que habíamos obtenido al final de este post, deducimos que tan solo tenemos que probar 9*15 = 135 candidatos para obtener los de 9 cifras. Y, así, poco a poco, vamos aumentando la lista hasta llegar a nuestro objetivo, las 15 cifras. Como hacerlo a mano puede resultar bastante engorroso, de nuevo emplearemos un programa en JavaScript. Al igual que en el otro post, si no sabes de programación, no te preocupes, sáltate esta parte y ve directo al final, a probar el programa tú mismo.

En esta ocasión, necesitaremos tener un vector con todos los números automórficos de menos cifras que los que se están buscando, por lo que crearemos un vector solution, formado por otros vectores, uno para cada longitud. Por ejemplo, para 3 cifras, solution es [[1, 5, 6], [25, 76], [625, 376]]. En cada paso, iremos añadiendo otro vector con más números. Al principio del programa, lo inicializamos a simplemente los números de 1 cifra:

var solution = [[1, 5, 6]];

Al igual que en nuestro anterior programa, éste también funcionará con un parámetro, maxCifras, que es el número de dígitos hasta el cual queremos encontrar números automórficos. Así, pues, comenzamos un bucle para encontrar los números desde 2 cifras (recuerda que los de 1 cifra ya están en solution) hasta maxCifras.

for(cifras = 2; cifras <= maxCifras; cifras++){
  ...
}

Ahora, vamos mirando uno a uno los conjuntos de soluciones que tenemos para números menores y vamos tomando cada uno de sus números. Por ejemplo, para hallar los de 4 cifras, deberíamos mirar primero los de 1, [1, 5, 6], e ir chequeando el 1, el 5 y el 6; después iríamos a los de 2 cifras, [25, 76], y comprobaríamos el 25 y el 76; y, por último, tomaríamos el vector de los de 3 cifras, [625, 376], y comprobaríamos el 625 y el 376.

  for(cifrasMenores = 1; cifrasMenores < cifras; cifrasMenores++){
    len = solution[cifrasMenores-1].length;
    for(i = 0; i < len; i++){
      temp = solution[cifrasMenores-1][i];
      ...
    }
  }

Con cada uno de estos números, hacemos la comprobación que decíamos al principio del post: tenemos que precederlo por cada uno de los dígitos del 1 al 9 y ver si se cumple la condición de automórfico. Si así es, sólo tenemos que añadirlo a un vector temporal que, cuando terminemos de encontrar todos los números de estas cifras, añadiremos a la solución. Para la condición de automórfico, mantenemos la que encontramos en el otro programa, que funcionaba bien.

      for(j = 1; j <= 9; j++){
        temp += (10**(cifras-1));
        if(BigInt(temp)**BigInt(2)%BigInt(10**(cifras)) == temp){
          solutionTemp.push(temp);
        }
      }

Además, hay que tener en cuenta que para cada número de cifras, debemos "vaciar" el vector temporal al inicio de la iteración. El programa completo es:

function automorficosHasta(maxCifras){
  var i, j, solution = [[1, 5, 6]], cifras, cifrasMenores, solutionTemp, len, temp;
  for(cifras = 2; cifras <= maxCifras; cifras++){
    solutionTemp = [];
    for(cifrasMenores = 1; cifrasMenores < cifras; cifrasMenores++){
      len = solution[cifrasMenores-1].length;
      for(i = 0; i < len; i++){
        temp = solution[cifrasMenores-1][i];
        for(j = 1; j <= 9; j++){
          temp += (10**(cifras-1));
          if(BigInt(temp)**BigInt(2)%BigInt(10**(cifras)) == temp){
            solutionTemp.push(temp);
          }
        }
      }
    }
    solution.push(solutionTemp);
  }
  console.log(solution);
}

Como este algoritmo es mucho más eficiente, este programa funciona mejor que el otro. No requiere más que de unas décimas de segundo para calcular todos los números automórficos de hasta 16 cifras, cosa inimaginable con lo que teníamos hasta ahora.

Si quieres probar tú mismo la eficacia de este programa, escribe el número de cifras hasta las que quieras que busque números automórficos y dale al botón.

 

Por fin podemos resolver nuestro problema. Todos los números automórficos de 15 cifras o menos son (aquí están bien ordenados):

1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, 2890625, 7109376, 12890625, 87109376, 212890625, 787109376, 1787109376, 8212890625, 18212890625, 81787109376, 918212890625, 9918212890625, 40081787109376, 59918212890625, 259918212890625, 740081787109376

Indagando un poco en Internet, podemos llegar a esta página con la lista de los primeros números automórficos y comprobamos que nuestro resultado es correcto.

No ha sido fácil, pero hemos llegado al final. Espero que te hayan parecido interesantes estos cuatro posts divulgativos y que te haya entrado el gusanillo por la teoría de números. Hay muchos números con propiedades muy curiosas esperándote.

---

Aunque el algoritmo que tenemos nos sirve para lo que queríamos hacer, a continuación, puedes probar otro algoritmo aún más rápido, según la discusión en los comentarios. Con éste, puedes hallar muchos más números.