¿Cómo encontrar el quinto número perfecto (que es 33550336)? El problema está tardando una eternidad en ejecutarse

Solución:

Comprobemos las propiedades de un número perfecto. Esta pregunta de desbordamiento matemático nos dice dos cosas muy interesantes:

1. Un número perfecto nunca es un cuadrado perfecto.
2. Un número perfecto tiene la forma (2^k-1) × (2^k-1).

El 2^{Dakota del Norte} El punto es muy interesante porque reduce nuestro campo de búsqueda a apenas nada. Un int en Java es de 32 bits. Y aquí vemos una correlación directa entre potencias y posiciones de bits. Gracias a esto, en lugar de realizar millones y millones de llamadas a isPerfectNumber, haremos menos de 32 para encontrar el 5^th número perfecto.

Así que ya podemos cambiar el campo de búsqueda, ese es tu bucle principal.

    int count = 0;
    for (int k = 1; count < 5; k++) {

      // Compute candidates based on the formula.
      int candidate = (1L << (k - 1)) * ((1L << k) - 1);

      // Only test candidates, not all the numbers.
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }

Esta es nuestra gran victoria. Ninguna otra optimización superará a esta: ¿por qué probar 33 millones de números, cuando puede probar menos de 100?

Pero a pesar de que tenemos una gran mejora, su aplicación en su conjunto aún se puede mejorar, es decir, su método isPerfectNumber(int).

Actualmente, todavía estás probando demasiados números. Un número perfecto es la suma de todos los divisores propios. Así que si d divide n, n/d también divide n. Y puede agregar ambos divisores a la vez. Pero la belleza es que puedes detenerte en sqrt(n), porque sqrt(n)*sqrt(n) = n, matemáticamente hablando. Entonces, en lugar de probar n divisores, solo probarás sqrt(n) divisores.

Además, esto significa que debe comenzar a pensar en casos de esquina. Los casos de las esquinas son 1 y sqrt(n):

• 1 es un caso de esquina porque si divides n por 1, usted obtiene n pero no agregas n para comprobar si n es un número perfecto. Tu solo agregas 1. Entonces probablemente comenzaremos nuestra suma con 1 solo para evitar demasiados ifs.
• sqrt(n) es un caso de esquina porque tendríamos que comprobar si sqrt(n) es un número entero o no y es tedioso. PERO la pregunta de desbordamiento matemático a la que hice referencia dice que ningún número perfecto es un cuadrado perfecto, por lo que facilita nuestra condición de bucle.

Entonces, si en algún momento sum se vuelve mayor que n, nosotros podemos parar. La suma de los divisores propios es mayor que n indica que n es abundante y, por lo tanto, no es perfecto. Es una pequeña mejora, pero muchos candidatos son abundantes. Así que probablemente ahorrará algunos ciclos si lo mantiene.

Por último, tenemos que ocuparnos de un pequeño problema: el número 1 como candidato. 1 es el primer candidato y aprobará todas nuestras pruebas, por lo que tenemos que presentar un caso especial para ello. Agregaremos esa prueba al comienzo del método.

Ahora podemos escribir el método de la siguiente manera:

  static boolean isPerfectNumber(int n) {
    // 1 would pass the rest because it has everything of a perfect number
    // except that its only divisor is itself, and we need at least 2 divisors.
    if (n < 2) return false;
   

    // divisor 1 is such a corner case that it's very easy to handle:
    // just start the sum with it already.
    int sum = 1;

    // We can stop the divisors at sqrt(n), but this is floored.
    int sqrt = (int)Math.sqrt(n);

    // A perfect number is never a square.
    // It's useful to make this test here if we take the function
    // without the context of the sparse candidates, because we
    // might get some weird results if this method is simply
    // copy-pasted and tested on all numbers.
    // This condition can be removed in the final program because we
    // know that no numbers of the form indicated above is a square.
    if (sqrt * sqrt == n) {
      return false;
    }
    
    // Since sqrt is floored, some values can still be interesting.
    // For instance if you take n = 6, floor(sqrt(n)) = 2, and
    // 2 is a proper divisor of 6, so we must keep it, we do it by
    // using the <= operator.
    // Also, sqrt * sqrt != n, so we can safely loop to sqrt
    for (int div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        // Add both the divisor and n / divisor.
        sum += div + n / div;
        // Early fail if the number is abundant.
        if (sum > n) return false;
      }
    }
    return n == sum;
  }

Estas son optimizaciones tales que incluso puedes encontrar las 7^th número perfecto en menos de un segundo, con la condición de que adapte el código para longs en lugar de ints. Y aún podrías encontrar el 8^th en 30 segundos.

Así que aquí está ese programa (pruébelo en línea). Eliminé los comentarios ya que las explicaciones están aquí arriba.

public class Main {
  public static void main(String[] args) {
    int count = 0;
    for (int k = 1; count < 8; k++) {
      long candidate = (1L << (k - 1)) * ((1L << k) - 1);
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }
  }

  static boolean isPerfectNumber(long n) {
    if (n < 2) return false;
    long sum = 1;
    long sqrt = (long)Math.sqrt(n);
    for (long div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        sum += div + n / div;
        if (sum > n) return false;
      }
    }
    return n == sum;
  }
}

El resultado del programa anterior es la lista de los primeros 8 números perfectos:

6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128

Puede encontrar una mayor optimización, especialmente en la búsqueda, si comprueba si 2^k-1 es primo o no como dice Eran en su respuesta, pero dado que tenemos menos de 100 candidatos para longs, no me parece útil ganar potencialmente algunos milisegundos porque la computación de números primos también puede ser costosa en este programa. Si desea buscar números primos perfectos más grandes, tiene sentido, pero ¿aquí? No: agrega complejidad y traté de mantener estas optimizaciones bastante simples y directas.

Hay algunas heurísticas para romper antes de los bucles, pero encontrar el quinto número perfecto todavía me tomó varios minutos (probé heurísticas similares a las sugeridas en las otras respuestas).

Sin embargo, puede confiar en la prueba de Euler de que todos los números perfectos pares (y aún se desconoce si hay números perfectos impares) tienen la forma:

2^i-1(2^I-1)

donde tanto yo como 2^I-1 debe ser primo.

Por lo tanto, puede escribir el siguiente ciclo para encontrar los primeros 5 números perfectos muy rápidamente:

int counter = 0,
i = 0;

while (counter != 5) {
    i++;
    if (isPrime (i)) {
        if (isPrime ((int) (Math.pow (2, i) - 1))) {
            System.out.println ((int) (Math.pow (2, i -1) * (Math.pow (2, i) - 1)));
            counter++;
        }
    }
}

Producción:

6
28
496
8128
33550336

Puedes leer más sobre esto aquí.

Si cambia de int para long, puedes usar este ciclo para encontrar los primeros 7 números perfectos muy rápidamente:

6
28
496
8128
33550336
8589869056
137438691328

los isPrime el método que estoy usando es:

public static boolean isPrime (int a)
{
  if (a == 1)
    return false;
  else if (a < 3)
    return true;
  else {
    for (int i = 2; i * i <= a; i++) {
      if (a % i == 0)
        return false;
    }
  }
  return true;
}

---

---

Utiliza Nuestro Buscador