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(3, n)]:
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.
[EDIT]
La ejecución del código original con n = 10_000
arroja
Tiempo : 58 segundos
Iteraciones: 49.985.000 iteraciones
3 1.0
5 1.0
7 0.6666666666666666
11 1.0
17 1.0
41 1.0
47 0.5652173913043478
59 0.5862068965517241
67 0.5454545454545454
101 0.68
107 0.6698113207547169
161 0.50625
221 0.5863636363636363
227 0.584070796460177
347 0.5057803468208093
377 0.5079787234042553
set
para no tener duplicados. Por otro lado, envalues
usas una lista y según recuerdo de mis clases, existen las funciones generadoras que son más "aptas" para calcular muchos valores.for k in values:
podría tener una condición de parada cuando eso ya es imposible que se produzca. Digamos que son 1000 valores y ya llevas comprobados 600 y has encontrado 99, tu criterio de aceptación nunca se va a cumplir, porque en el mejor de los casos vas a encontrar 499, así que le pones una condición de parada y te ahorras 400 iteraciones.pi(x)
, que da el número de aproximado de primos desde 1 hastax
. t5k.org/howmany.html