Skip to main content
3 de 4
Agrega métrica.
Candid Moe
  • 26.6k
  • 10
  • 23
  • 47

¿Cómo optimizar implementación de Euler's Lucky Numbers?

Referencia: Este pregunta está inspirada en el código publicado por Matt Parker en el canal Numberphile de YT, en un video llamado Caboose Numbers.

introducir la descripción de la imagen aquí

La secuencia entera

n ** 2 - n + C, para n=1, 2, ... C - 1

produce números primos para 6 valores de C (2, 3, 5, 11, 17 y 41). Para otros valores de C, la secuencia produce una combinación de primos y valores compuestos.

El objetivo del código es probar todos los valores C entre 1 y 1.000.000.000 para identificar aquellos que producen secuencias con más primos que compuestos (if tada > 0.5:).

He transcrito el código publicado eliminando las grabaciones de los resultados, para simplificarlo:

import sympy

n = 1_000_000_000

for i in [i for i in range(1, 3)]:
    values = [j**2 - j + i for j in range(1,i)]
    primes = 0
    for k in values:
        if sympy.isprime(k):
            primes += 1
    tada = primes/len(values)
    if tada > 0.5:
        print(f"{i} {tada}")

Hay dos tipos de optimización posible. La primera es de tipo "aritmética". Por ejemplo, dado que la expresión se puede reescribir como

n * (n - 1) + C

está claro que n * (n - 1) siempre será par, pues al menos uno de los factores es par. En consecuencia, cuando C es par, la expresión producirá sólo valores pares, sin ningún valor primo. Puedo optimizar cambiando el for externo para saltarme los valores de C pares. Así se reduce a la mitad el número de iteraciones.

El segundo tipo de optimización, que busco aquí, es de implementación en Python. Por ejemplo, el for más externo se puede sustituir por

for i in range(3, n):

con lo que se evita generar y procesar una lista de 1.000 millones de elementos en RAM.

O, mejor, puede escribir

for i in range(3, n, 2):

para evitar los valores pares.

La pregunta es: ¿Qué cambios puedo hacer en la implementación para optimizar su tiempo de ejecución? Por ejemplo, podría usar valores precomputados en alguna lista, set o diccionario para no tener que repetir la consulta sympy.isprime(k) un millón de veces para un mismo valor de k.

[EDIT] La métrica a usar es el número final de iteraciones en el for más interno, para descontar diferencias por tamaño de la RAM o velocidad de la CPU.

Candid Moe
  • 26.6k
  • 10
  • 23
  • 47