Tamiz de Pritchard

En matemáticas , la criba de Pritchard es un algoritmo para hallar todos los números primos hasta un límite especificado. Al igual que la antigua criba de Eratóstenes , tiene una base conceptual sencilla en la teoría de números . ^{[ 1 ]} Es especialmente adecuada para cálculos manuales rápidos con límites pequeños.

Mientras que la criba de Eratóstenes descarta cada número no primo para cada uno de sus factores primos, la criba de Pritchard evita considerar casi todos los números no primos mediante la construcción de ruedas progresivamente más grandes, que representan el patrón de números no divisibles por ninguno de los primos procesados ​​hasta el momento. De este modo, logra una mejor complejidad asintótica y fue la primera criba con un tiempo de ejecución sublineal en el límite especificado. Su tiempo de ejecución asintótico no ha sido mejorado y elimina menos compuestos que cualquier otra criba conocida. Fue creada en 1979 por Paul Pritchard. ^{[ 2 ]}

Dado que Pritchard ha creado varios otros algoritmos de criba para encontrar números primos, ^{[ 3 ] [ 4 ] [ 5 ]} la criba de Pritchard a veces se destaca por ser llamada la criba de rueda (por el propio Pritchard ^{[ 1 ]} ) o la criba de rueda dinámica . ^{[ 6 ]}

Un número primo es un número natural que no tiene divisores naturales aparte del número 1 y él mismo.

Para encontrar todos los números primos menores o iguales a un entero N dado , un algoritmo de criba examina un conjunto de candidatos en el rango 2, 3, ... , N , y elimina los que no son primos, dejando los primos al final. La criba de Eratóstenes examina todo el rango, eliminando primero todos los múltiplos del primer primo 2, luego del siguiente primo 3, y así sucesivamente. La criba de Pritchard, en cambio, examina un subconjunto del rango que consiste en números que aparecen en ruedas sucesivas, que representan el patrón de números que quedan después de que cada primo sucesivo sea procesado por la criba de Eratóstenes.

Para i > 0 , la i -ésima rueda W _i representa este patrón. Es el conjunto de números entre 1 y el producto P _i = p ₁ · p ₂ ⋯ p _i de los primeros i números primos que no son divisibles por ninguno de estos números primos (y se dice que tiene una longitud asociada P _i ). Esto se debe a que sumar P _i a un número no cambia si es divisible por uno de los primeros i números primos, ya que el resto de la división por cualquiera de estos primos no cambia.

Así, W ₁ = {1} con longitud P ₁ = 2 representa el patrón de números impares; W ₂ = {1,5} con longitud P ₂ = 6 representa el patrón de números no divisibles por 2 o 3; etc. Las ruedas se llaman así porque W _i se puede visualizar como un círculo de circunferencia P _i con sus lados marcados a sus distancias correspondientes desde un origen. Al hacer rodar la rueda a lo largo de la recta numérica, se marcan puntos que corresponden a números sucesivos no divisibles por ninguno de los primeros i números primos. La animación muestra cómo W ₂ se hace rodar hasta 30.

Resulta útil definir W _i → n para n > 0 como el resultado de extender W _i hasta n . Entonces la animación genera W ₂ → 30 = {1,5,7,11,13,17,19,23,25,29} . Nótese que hasta 5 ² − 1 = 24 , esto consiste únicamente en 1 y los primos entre 5 y 25.

La criba de Pritchard se deriva de la observación ^{[ 1 ]} de que esto se cumple en general: para todo i > 0 , los valores en W _i → ( p ² _{i +1} − 1) son 1 y los primos entre p _{i +1} y p ² _{i +1} . Incluso se cumple para i = 0 , donde la rueda tiene longitud 1 y contiene solo 1 (que representa todos los números naturales). Así, la criba de Pritchard comienza con la rueda trivial W ₀ y construye ruedas sucesivas hasta que el cuadrado del primer miembro de la rueda después de 1 sea al menos N. Las ruedas crecen muy rápidamente, pero solo se necesitan y generan sus valores hasta N.

Queda por encontrar un método para generar la siguiente rueda. Nótese en la animación que W ₃ = {1,5,7,11,13,17,19,23,25,29} − {5 · 1 , 5 · 5} se puede obtener haciendo rodar W ₂ hasta 30 y luego eliminando 5 veces cada miembro de W ₂ . Esto también se cumple en general: para todo i ≥ 0 , W _{i +1} = ( W _i → P _{i +1} ) − { p _{i +1} · w | w ∈ W _i } . ^{[ 1 ]} Hacer rodar W _i más allá de P _i simplemente añade valores a W _i , por lo que la rueda actual se extiende primero obteniendo cada miembro sucesivo comenzando con w = 1 , sumándole P _i y insertando el resultado en el conjunto. Luego se eliminan los múltiplos de p _{i +1} . Se debe tener cuidado de evitar que se elimine un número que a su vez deba multiplicarse por p _{i +1} . La criba de Pritchard, tal como se presentó originalmente ^{[ 2 ],} realiza primero las eliminaciones saltándose los elementos sucesivos hasta encontrar el máximo necesario, y luego recorriendo el conjunto en orden inverso. Este es el método utilizado en la primera animación anterior. Un enfoque más sencillo consiste en reunir los múltiplos de p _{i +1} en una lista y luego eliminarlos. ^{[ 7 ]} Gries y Misra proponen otro enfoque. ^{[ 8 ]}

Si el bucle principal termina con una rueda cuya longitud es menor que N , se extiende hasta N para generar los primos restantes.

Por lo tanto , el algoritmo para encontrar todos los números primos hasta N es el siguiente:

1. Comience con un conjunto W = {1} y longitud = 1 que representa la rueda 0, y primo p = 2 .
2. Siempre que p ² ≤ N , haga lo siguiente:
   1. si longitud < N , entonces
      1. extender W obteniendo repetidamente miembros sucesivos w de W comenzando con 1 e insertando longitud + w en W siempre que no exceda p · longitud o N ;
      2. aumentar la longitud hasta el mínimo de p · longitud y N.
   2. Elimine repetidamente p veces cada miembro de W , primero encontrando la longitud ≤ más grande y luego trabajando hacia atrás.
   3. anote el número primo p , luego establezca p al siguiente miembro de W después de 1 (o 3 si p era 2).
3. si length < N , entonces extiende W a N obteniendo repetidamente miembros sucesivos w de W comenzando con 1 e insertando length + w en W mientras no exceda N ;
4. Al finalizar, el resto de los números primos hasta N son los miembros de W después del 1.

 1

 1 2

 1 2 3 5

 1 2 3 5 7 11 13 17 19 23 25 29

 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149

 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149

El tamiz de Pritchard se puede expresar en pseudocódigo de la siguiente manera: ^{[ 1 ]}

El algoritmo Criba de Pritchard tiene como entrada : un número entero N >= 2. La salida es: el conjunto de números primos en {1,2,..., N }. Sean W y Pr conjuntos de valores enteros , y todas las demás variables valores enteros . k , W , length , p , Pr := 1, {1}, 2, 3, {2}; { invariante : p = p k +1 y W = W k${\displaystyle \cap }${1,2,..., N } y longitud = mínimo de P k , N y Pr = los primos hasta p k } mientras p 2 <= N hacer si ( longitud < N ) entonces Extender W , longitud al mínimo de p * longitud , N ; Eliminar los múltiplos de p de W ; Insertar p en Pr ; k , p := k + 1, siguiente( W , 1) si ( longitud < N ) entonces Extender W , longitud a N ; devolver Pr${\displaystyle \cup }$W - {1};

donde next(W, w) es el siguiente valor en el conjunto ordenado W después de w .

El procedimiento Extender W , longitud a n es { en: W = W k y longitud = P k y n > longitud } { salida: W = W k${\displaystyle \rightarrow }$n y longitud = n } entero w, x;  w , x := 1, longitud +1;  mientras x <= n hacer Insertar x en W ;  w := next( W , w );  x := longitud + w ;  longitud := n ;

procedimiento Eliminar múltiplos de p de W , longitud es entero w; w := p ; mientras p * w <= longitud hacer w := next( W , w ); mientras w > 1 hacer w := prev( W , w ); Eliminar p * w de W ;

donde prev(W, w) es el valor anterior en el conjunto ordenado W antes de w . El algoritmo puede inicializarse con W ₀ en lugar de W ₁ con la pequeña complicación de hacer next(W, 1) un caso especial cuando k = 0 .

Este algoritmo abstracto utiliza conjuntos ordenados que admiten las operaciones de inserción de un valor mayor que el máximo, eliminación de un miembro, obtención del siguiente valor después de un miembro y obtención del valor anterior a un miembro. Utilizando uno de los teoremas de Mertens (el tercero), se puede demostrar que utiliza O ( N /log log N ) de estas operaciones, sumas y multiplicaciones. ^{[ 2 ]}

Una lista doblemente enlazada basada en arreglos s puede usarse para implementar el conjunto ordenado W , donde s[w] almacena next(W,w) y s[w-1] almacena prev(W,w) . Esto permite que cada operación abstracta se implemente en un pequeño número de operaciones. (El arreglo también puede usarse para almacenar el conjunto Pr "gratis"). Por lo tanto, la complejidad temporal de la criba de Pritchard para calcular los primos hasta N en el modelo de máquina de acceso aleatorio es O ( N /log log N ) operaciones en palabras de tamaño O (log N ) . Pritchard también muestra cómo se pueden eliminar las multiplicaciones usando tablas de multiplicación muy pequeñas, ^{[ 2 ]} por lo que la complejidad de bits es O ( N log N /log log N ) operaciones de bits.

En el mismo modelo, la complejidad espacial es O ( N ) palabras, es decir, O ( N log N ) bits. La criba de Eratóstenes requiere solo 1 bit para cada candidato en el rango de 2 a N , por lo que su complejidad espacial es menor, de O ( N ) bits. Nótese que el espacio necesario para los números primos no se cuenta, ya que pueden imprimirse o escribirse en almacenamiento externo a medida que se encuentran. Pritchard ^{[ 2 ]} presentó una variante de su criba que requiere solo O ( N /log log N ) bits sin comprometer la complejidad temporal sublineal, lo que la hace asintóticamente superior a la versión natural de la criba de Eratóstenes tanto en tiempo como en espacio.

Sin embargo, la criba de Eratósteos puede optimizarse para requerir mucha menos memoria operando sobre segmentos sucesivos de los números naturales. ^{[ 9 ]} Su complejidad espacial puede reducirse a O ( √ N ) bits sin aumentar su complejidad temporal. ^{[ 3 ]} Esto significa que, en la práctica, puede utilizarse para límites N mucho mayores de los que cabrían en la memoria, y también aprovechar la memoria caché rápida. Para obtener la máxima velocidad, también se optimiza utilizando una rueda pequeña para evitar el cribado con los primeros primos (aunque esto no cambia su complejidad temporal asintótica). Por lo tanto, la criba de Pritchard no es competitiva como criba práctica en rangos suficientemente grandes.

En el núcleo del tamiz de Pritchard se encuentra un algoritmo para construir ruedas sucesivas. Tiene un modelo geométrico simple como el siguiente:

1. Comience con un círculo de circunferencia 1 con una marca en 1.
2. Para generar la siguiente rueda:
   1. Recorre la rueda y encuentra (la distancia a) la primera marca después de 1; llámala p .
   2. Crea un nuevo círculo con una circunferencia p veces mayor que la de la rueda actual.
   3. Haz girar la rueda actual alrededor del nuevo círculo, marcándolo donde una marca lo toque.
   4. Amplíe la rueda actual por p y elimine las marcas que coincidan.

Para las dos primeras iteraciones es necesario continuar dando vueltas en círculo hasta llegar de nuevo al número 1.

El primer círculo representa W ₀ = {1} , y los círculos sucesivos representan las ruedas W ₁ , W ₂ , … . La animación de la derecha muestra este modelo en acción hasta W ₃ .

Del modelo se desprende que las ruedas son simétricas. Esto se debe a que P _k − w no es divisible por ninguno de los primeros k primos si y solo si w no es divisible por ellos. Es posible aprovechar esta característica para evitar procesar algunos números compuestos, pero a costa de un algoritmo más complejo.

Una vez que la rueda en el tamiz de Pritchard alcanza su tamaño máximo, las operaciones restantes son equivalentes a las realizadas por el tamiz de Euler .

El tamiz de Pritchard es único por combinar el conjunto de candidatos primos con una rueda dinámica utilizada para acelerar el proceso de tamizado. Pero una rueda estática separada (como la que se usa frecuentemente para acelerar el tamiz de Eratóstenes) puede dar una aceleración de O (log log N ) a este último, o a tamices lineales, siempre que sea lo suficientemente grande (en función de N ). Ejemplos son el uso de la rueda más grande de longitud que no exceda √ N / log ² N para obtener una versión del tamiz de Eratóstenes que toma O ( N ) adiciones y requiere solo O ( √ N / log log N ) bits, ^{[ 3 ]} y la aceleración del tamiz naturalmente lineal de Atkin para obtener una versión optimizada sublineal.

Bengalloun encontró una criba incremental suave lineal, ^{[ 10 ]} es decir, una que (en teoría) puede ejecutarse indefinidamente y requiere un número limitado de operaciones para incrementar el límite actual N. También mostró cómo hacerla sublineal adaptando la criba de Pritchard para construir incrementalmente la siguiente rueda dinámica mientras se usa la actual. Pritchard ^{[ 5 ]} mostró cómo evitar las multiplicaciones, obteniendo así la misma complejidad asintótica de bits que la criba de Pritchard.

Runciman proporciona un algoritmo funcional ^{[ 11 ]} inspirado en el tamiz de Pritchard.

• El tamiz de Eratóstenes
• Tamiz de Atkin
• Teoría del tamiz
• factorización de ruedas