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.
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.