6

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(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
7
  • No soy experto en este tipo de algoritmos, pero me parece que si vas a calcular varias veces ciertos números deberías de almacenarlos, si están pues aumentas el contador, si no están los agregas a la lista, como mencionas podrías usar un set para no tener duplicados. Por otro lado, en values usas una lista y según recuerdo de mis clases, existen las funciones generadoras que son más "aptas" para calcular muchos valores.
    – René
    Commented el 20 jun. a las 10:01
  • 1
    Estas buscando un C que produzca más del 50% de número primos, entonces este for: 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.
    – Yussef
    Commented el 20 jun. a las 10:28
  • @Yussef. Correcto. Un refinamiento es usar la función pi(x), que da el número de aproximado de primos desde 1 hasta x. t5k.org/howmany.html
    – Candid Moe
    Commented el 20 jun. a las 10:35
  • @René. Entre 1 y 1.000.000.000 hay alrededor de 48 millones de primos, y no hay memoria que aguante. Claro que siempre se puede precomputar un subrango, por ejemplo, los primos entre 1 y 100.000, lo cual es útil.
    – Candid Moe
    Commented el 20 jun. a las 10:49
  • @CandidMoe Son menos de 200MB, no es tanto
    – Yussef
    Commented el 20 jun. a las 10:54

1 respuesta 1

0

Esto es lo que he logrado. Creo que hay espacio para mejorar.

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")

Optimizaciones:

  1. Saltarse todos los pares en el for exterior.
  2. Precomputar los primos bajo 10 millones para no tener que evaluar sympy.isprime() una y otra vez para el mismo valor.
  3. Abandonar el for interior tan pronto quede claro que no llegamos al umbral requerido (tada > 0.5). Este chequeo puede hacerse para cada iteración del for interno; aunque reduce ligeramente el número de iteraciones, incrementa el tiempo de ejecución.
  4. En lugar de range(1, i) en el for interno, uso una función generadora gensec(i, factores) para saltar valores con factores primos comunes a 'i'.

La función generadora recibe la lista de factores primos de i. Al iterar, la función descarta todos los valores que sean múltiplos de algun factor, pues en ese caso, la expresión

k = j * j - j + i  

es divisible por al menos un factor primo, por lo que k no es primo.

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 : < 1 segundo

Iteraciones: 80.397 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
0 s,  80397 iteraciones    

Process finished with exit code 0
2
  • Hice unas pruebas en C#, y cargué los primos menores a 1 millón en un HashSet y en principio no vi mucha diferencia, por ahora diré que no aporta mucho (cuando tenga más tiempo haré otras pruebas con esto). Para el primer for usé Parallel.For (no sé si en python habrá algo similar) y esto sí que aceleró el asunto, con n=10.000 demora 58ms. También quiero probar con una función isPrime mejorada, se me ocurre evaluar previamente (antes de la iteración) si el número es divisible por 5 (termina en 5) o si es divisible por 3 y 9 (la suma de sus cifras)
    – Yussef
    Commented el 20 jun. a las 22:55
  • @yussef. Ahora busco una función generadora como range(1,n) que reciba además una lista de factores primos. La función debe excluir los resultados que sean múltiplos de algún factor. Esto reduciría la cantidad de valores a examinar en el for interno. Ejemplo: range2(1, 20, [2,3,5]) producirá 1, 7, 11, 13, 17, 19. El detalle está como obtener los factores primos de cada número.
    – Candid Moe
    Commented el 21 jun. a las 8:29

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.