Números automórficos- parte 2

En el anterior post, definimos los que son los números automórficos (su cuadrado termina con el propio número). Intentaremos ahora resolver el problema de encontrar todos los que tengan 15 cifras o menos.

Vamos a probar con los de 1 cifra:

• 1² = 1, que acaba en 1 --> Es automórfico.


• 2² = 4, que NO acaba en 2 --> No es automórfico.


• 3² = 9, que NO acaba en 3 --> No es automórfico.


• 4² = 16, que NO acaba en 4 --> No es automórfico.


• 5² = 25, que acaba en 5 --> Es automórfico.


• 6² = 36, que acaba en 6 --> Es automórfico.


• 7² = 49, que NO acaba en 7 --> No es automórfico.


• 8² = 64, que NO acaba en 8 --> No es automórfico.


• 9² = 81, que NO acaba en 9 --> No es automórfico.

Por lo tanto, los números automórficos de 1 cifra son: 1, 5 y 6.

El algoritmo está bastante claro: vamos mirando uno por uno y comprobando cómo termina el cuadrado. ¿Sabrías encontrar de esta manera todos los números automórficos de 2 cifras? Habría que empezar de la manera:

• 10² = 10, que NO acaba en 10 --> No es automórfico.


• 11² = 121, que NO acaba en 11 --> No es automórfico.


• ...

Como es algo tedioso, vamos a implementar ese algoritmo en JavaScript, para que sea el ordenador el que haga las cuentas. No pasa nada si no sabes cómo funciona este lenguaje, es tan solo una manera de hacerlo y puedes saltarte esta parte (simplemente ten fe de que funciona) e ir directamente a probarlo al final del post.

Para empezar, nuestro programa tendrá como parámetro el número de cifras de los números que queremos encontrar, que llamaremos cifras.

Los números que tienen m dígitos son los comprendidos entre 10^m-1 y 10^m, por lo que tiene sentido definir la cota inferior así y comenzar un bucle:

init = 10**(cifras-1);
for(i = init; i < 10*init; i++){
  ...
}

Dentro del bucle, tendremos que comprobar que el cuadrado del número i termina por i, es decir, que i² ≡ i (mod 10^cifras):

  if((i**2)%(10*init) == i){
    solution.push(i);
  }

La función entera sería:

function automorficos(cifras){
  var i, solution = [];
  var init = 10**(cifras-1);
  for(i = init; i < 10*init; i++){
    if((i**2)%(10*init) == i){
      solution.push(i);
    }
  }
  console.log(solution);
}

Y si queremos la lista completa de los números automórficos que tengan tantas cifras o menos, basta con introducir un nuevo bucle que contemple el número de cifras:

function automorficosHasta(maxCifras){
  var i, solution = [], cifras, init;
  for(cifras = 1; cifras <= maxCifras; cifras++){
    init = 10**(cifras-1);
    for(i = init; i < 10*init; i++){
      if((i**2)%(10*init) == i){
        solution.push(i);
      }
    }
  }
  console.log(solution);
}

Así, automorficosHasta(2) daría como resultado [1, 5, 6, 25, 76], que son los tres números que habíamos encontrado antes y otros dos nuevos de 2 cifras. Si queremos calcular todos los que tengan 4 cifras o menos, automorficosHasta(4) devuelve [1, 5, 6, 25, 76, 376, 625, 9376].

Este programa funciona bastante bien para números pequeños pero en cuanto el parámetro crece, surgen dos principales problemas. Primero, cada vez hay más números que comprobar y tarda más y más tiempo. Para automorficosHasta(9) ya tarda casi 30 segundos, y ese tiempo es muchísimo mayor para automorficosHasta(10). Nuestro objetivo de conseguir automorficosHasta(15) no parece muy factible. Segundo, para números muy grandes, la memoria es insuficiente y el ordenador se ve forzado a hacer algunos redondeos que, a la larga, afectan al resultado. Por esto mismo, hay algunos números que deberían aparecer en la lista pero no lo hacen. Para solucionar este segundo problema, haremos uso de otro "tipo de número" de JavaScript llamado BigInt y que está especializado en trabajar con números muy grandes sin perder tanta precisión. Esto se traduce en nuestro programa en cambiar la línea del condicional por esta otra:

if((BigInt(i)**BigInt(2))%(BigInt(10)*BigInt(init)) == i){

Es decir, cada vez que aparece un número en esa gran operación, lo precedemos por el BigInt. El programa queda:

function automorficosHasta(maxCifras){
  var i, solution = [], cifras, init;
  for(cifras = 1; cifras <= maxCifras; cifras++){
    init = 10**(cifras-1);
    for(i = init; i < 10*init; i++){
      if((BigInt(i)**BigInt(2))%(BigInt(10)*BigInt(init)) == i){
        solution.push(i);
      }
    }
  }
  console.log(solution);
}

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:

 

Hemos solucionado el segundo problema, pero hemos empeorado el primero: mayor precisión requiere mayor tiempo de cómputo. Ahora, automorficosHasta(8), que antes no tardaba más que un par de segundos, requiere de casi un minuto para devolver [1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, 2890625, 7109376, 12890625, 87109376].

¿Cómo podemos tener esperanzas de calcular automorficosHasta(15) si el tiempo crece de manera tan exponencial? Está claro que éste no es el camino adecuado. No obstante, tenemos ya unos cuantos números automórficos que pueden darnos información muy valiosa, como veremos en el siguiente post. ¿Te apetece intentar descubrir algún patrón entre los números antes de leerlo?

¡No te pierdas la tercera parte, en la que comenzamos a detectar patrones, lo cual nos lleva a un importante resultado!