import time
import sympy
def gensec(n: int, factores: list[int]):
# Función generadora que retorna la secuencia 1 a n
# excluyendo los múltiplos de los enteros de la
# lista de factores.
indices = factores.copy()
num_ind = len(indices)
for valor in range(1, n):
if valor in indices:
# Valor es múltiplo de alguno de los factores;
# descartarlo
for i in range(num_ind):
# Avanzar los indices para que todos sean
# mayores que 'valor'.
if indices[i] == valor:
indices[i] += factores[i]
else:
yield valor
preload_primes = 10_000_000
primes_set = {i for i in range(3, preload_primes, 2) if sympy.isprime(i)}
start = int(time.time())
n = 10_000
iteraciones = 0
for i in range(3, n, 2):
# Determinar los factores primos de i
factores = sympy.primefactors(i)
primes = 0
# Recorrer los enteros de 1 a i saltando todos
# los múltiplos de los factores primos de i.
for j in gensec(i, factores):
iteraciones += 1
k = j * j - j + i
if k in primes_set or (k > preload_primes and sympy.isprime(k)):
primes += 1
# ¿Cuantas iteraciones (y potenciales primos quedan)
potential_primes = (i - j + 1) // 2 # Descontar los pares
# Evaluar si podemos alcanzar tada > 0.5 en esta corrida
if (primes + potential_primes) <= 0.5 * (i - 1):
# No quedan suficientes primos para alcanzar tada > 0.5.
break
tada = primes / (i - 1)
if tada > 0.5:
print(f"{i} {tada}")
end = int(time.time())
print(int(end-start), "s, ", iteraciones, "iteraciones")
Probando con n = 10_000
y mi anciano tarro, obtengo estos resultados:
Mejoras pendientes
En el cálculo de potential_primes
hay que descontar todos los múltiplos de los factores primos en factores
. Por el momento, sólo descuento los valores pares.
Tiempo : 12 segundos< 1 segundo
Iteraciones: 12.09280.559397 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
120 s, 1209255980397 iteraciones
Process finished with exit code 0