factorización de ruedas

La factorización por rueda es un método para generar una secuencia de números naturales mediante sumas repetidas, determinadas por una serie de los primeros números primos , de manera que los números generados sean coprimos con estos primos, por construcción.

Para un número n elegido (generalmente no mayor que 4 o 5), los primeros n números primos determinan la forma específica de generar una secuencia de números naturales que se sabe de antemano que son coprimos con estos primos; es decir, se sabe que ninguno de ellos es múltiplo de ninguno de estos primos. Este método puede utilizarse, por lo tanto, para mejorar el método de división por tanteo para la factorización de enteros , ya que ninguno de los números generados necesita ser probado mediante divisiones por tanteo con esos primos pequeños.

El método de división por tanteo consiste en dividir el número a factorizar entre los enteros en orden creciente (2, 3, 4, 5, ...) sucesivamente. Una mejora común consiste en probar solo con primos, es decir, con 2, 3, 5, 7, 11, ... Con la factorización por rueda, se parte de una pequeña lista de números, llamada base (generalmente los primeros primos ); luego, se genera la lista, llamada rueda , de los enteros que son coprimos con todos los números de la base.

Para los números generados mediante el método de "rodar la rueda", basta con considerar como posibles factores los números primos que no pertenecen a la base. Es como si estos números generados ya hubieran sido probados y se hubiera comprobado que no son divisibles por ninguno de los primos de la base. Se trata de una optimización, ya que todas estas operaciones se vuelven redundantes y se evitan por completo.

Cuando se utiliza para encontrar números primos, o para realizar un cribado en general, este método reduce la cantidad de números candidatos que se consideran posibles primos. Con la base {2, 3}, la reducción es de 1/3 < 34% de todos los números. Esto significa que se omiten automáticamente 2/3 de todos los números candidatos. Las bases más grandes reducen aún más esta proporción; por ejemplo, con la base {2, 3, 5} a 8/30 < 27% , y con la base {2, 3, 5, 7} a 48/210 < 23% .

Cuanto más grande es la rueda, mayores son los recursos computacionales necesarios y menores las mejoras adicionales, lo que conlleva una rápida disminución de los beneficios.

Los números naturales a partir del 1 se enumeran mediante la suma repetida de 1:

1, 2, 3, 4, 5, ...

Considerados en intervalos de dos números cada uno, se enumeran mediante sumas repetidas de 2:

1, 2  ;  3, 4  ;  5, 6  ;  ...

Cada segundo número generado de esta manera será par. Por lo tanto, los números impares se generan mediante la suma repetida de 2:

1  ;  3  ;  5  ;  7  ;  ...

Considerados en grupos de tres números cada uno, se enumeran mediante sumas repetidas de 2 × 3 = 6:

1, 3, 5  ;  7, 9, 11  ;  ...

Cada segundo número en estas ternas será un múltiplo de 3, porque los números de la forma 3 + 6k son todos múltiplos impares de 3. Por lo tanto, todos los números coprimos con los dos primeros primos (2 y 3) se generarán mediante sumas repetidas de 6, comenzando desde {1, 5}:

1, 5  ;  7, 11  ;  13, 17  ;  ...

La misma secuencia se puede generar mediante sumas repetidas de 2 × 3 × 5 = 30, convirtiendo cada cinco intervalos consecutivos, de dos números cada uno, en un intervalo unido de diez números:

1, 5, 7, 11, 13, 17, 19, 23, 25, 29  ;  31, 35, 37, ...

De cada diez de estos números 6-coprimos, dos son múltiplos de 5, por lo tanto, los ocho restantes serán 30-coprimos:

1, 7, 11, 13, 17, 19, 23, 29  ;  31, 37, 41, 43, 47, 49, ...

Esto es, naturalmente, una generalización.

Lo anterior muestra las tres primeras ruedas:

• {1} (que contiene 1 = 2 − 1 número) con la "circunferencia" de 2 para generar la secuencia de 2-coprimos mediante la suma repetida de 2;
• {1, 5} (que contiene 2 = (2 − 1) × (3 − 1) números) con la "circunferencia" de 2 × 3 = 6, para generar la secuencia de números 6-coprimos mediante sumas repetidas de 6;
• {1, 7, 11, 13, 17, 19, 23, 29} (que contiene 8 = (2 − 1) × (3 − 1) × (5 − 1) números) con la "circunferencia" de 2 × 3 × 5 = 30, para generar la secuencia de 30 números coprimos mediante sumas repetidas de 30; etc.

Otra representación de estas ruedas consiste en convertir los números de una rueda, como se ve arriba, en una lista circular de las diferencias entre los números consecutivos, y luego generar la secuencia comenzando desde 1 sumando repetidamente estos incrementos uno tras otro al último número generado, indefinidamente. Esto es lo más cercano a la metáfora de hacer girar la rueda . Por ejemplo, esto convierte {1, 7, 11, 13, 17, 19, 23, 29, 31} en {6, 4, 2, 4, 2, 4, 6, 2}, y luego la secuencia se genera como

norte =1; norte +6=7; norte +4=11; norte +2=13; norte +4=17; norte +2=19; norte +4=23; norte +6=29; norte +2=31; norte +6=37; norte +4=41; norte +2=43; etc.

Con una base dada de los tres primeros números primos {2, 3, 5}, el "primer giro" de la rueda consiste en:

7, 11, 13, 17, 19, 23, 29, 31 .

La segunda vuelta se obtiene sumando 30, el producto de la base, a los números de la primera vuelta. La tercera vuelta se obtiene sumando 30 a la segunda vuelta, y así sucesivamente.

Para implementar el método, se puede observar que los incrementos entre dos elementos consecutivos de la rueda, es decir

inc = [4, 2, 4, 2, 4, 6, 2, 6],

permanecen iguales después de cada turno.

La implementación que se sugiere a continuación utiliza una función auxiliar `div(n,k) `, que comprueba si n es divisible exactamente por k , y devuelve `true` en ese caso y `false` en caso contrario. En esta implementación, el número a factorizar es `n` , y el programa devuelve el divisor más pequeño de `n` , devolviendo el propio `n` si es primo.

Si div( n , 2) = verdadero, entonces devuelve 2. Si div( n , 3) = verdadero, entonces devuelve 3. Si div( n , 5) = verdadero, entonces devuelve 5. k := 7; i := 0. Mientras k * k ≤ n , si div( n , k ) = verdadero, entonces devuelve k. k := k + inc[ i ]. Si i < 7 , entonces i := i + 1; de lo contrario , i := 0. Devuelve n.

Para obtener la factorización completa de un número entero, el cálculo puede continuarse sin reiniciar el proceso. Esto da como resultado el siguiente programa para la factorización completa, donde la función `add` agrega su primer argumento al final del segundo argumento, que debe ser una lista.

factores := [ ] mientras div( n , 2) = verdadero hacer factores := sumar(2, factores) n := n / 2 mientras div( n , 3) ​​= verdadero hacer factores := sumar(3, factores) n := n / 3 mientras div( n , 5) = verdadero hacer factores := sumar(5, factores) n := n / 5 k := 7; i := 0 mientras k * k ≤ n hacer si div( n , k ) = verdadero entonces agregar( k , factores) n := n / k sino k := k + inc[ i ] si i < 7 entonces i := i + 1 sino i := 0 si n > 1 entonces agregar( n , factores) devolver factores

La factorización por rueda se utiliza para generar listas de números mayoritariamente primos a partir de una fórmula matemática simple y una lista mucho más pequeña de los primeros números primos. Estas listas pueden utilizarse posteriormente en la división por tanteo o en el método de cribado . Dado que no todos los números de estas listas son primos, esto introduce operaciones redundantes e ineficientes. Sin embargo, los generadores en sí mismos requieren muy poca memoria en comparación con mantener una lista pura de números primos. La pequeña lista de números primos iniciales constituye los parámetros completos para que el algoritmo genere el resto de la lista. Estos generadores se denominan ruedas . Si bien cada rueda puede generar una lista infinita de números, a partir de cierto punto, los números dejan de ser mayoritariamente primos.

El método puede aplicarse recursivamente como un cribado de rueda de números primos para generar ruedas más precisas. Paul Pritchard ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} realizó un trabajo fundamental sobre la factorización de ruedas, los cribados que utilizan la factorización de ruedas y el cribado de ruedas, formulando una serie de algoritmos diferentes. Para visualizar el uso de una rueda de factorización, se puede comenzar escribiendo los números naturales alrededor de círculos, como se muestra en el diagrama adjunto. El número de radios se elige de manera que los números primos tiendan a acumularse en una minoría de los radios.

1. Encuentra los primeros números primos que forman la base de la rueda de factorización. Estos se conocen o se pueden determinar a partir de aplicaciones previas de ruedas de factorización más pequeñas o encontrándolos rápidamente usando la criba de Eratóstenes .
2. Multiplica los números primos de la base para obtener el resultado n , que es la circunferencia de la rueda de factorización.
3. Escribe los números del 1 al n dentro de un círculo. Este será el círculo interior, que representará una rotación de la rueda.
4. Desde los números del 1 al n en el círculo más interno, elimine todos los múltiplos de los números primos base del paso uno, tal como se aplicó en el paso 2. Esta eliminación de números compuestos se puede lograr mediante el uso de una criba como la de Eratóstenes o como resultado de la aplicación de ruedas de factorización más pequeñas.
5. Tomando x como el número de círculos escritos hasta ahora, continúe escribiendo xn + 1 a xn + n en círculos concéntricos alrededor del círculo más interno, de manera que xn + 1 esté en la misma posición que ( x − 1) n + 1 .
6. Repita el paso 5 hasta que el círculo de rotación más grande abarque el número más grande que se va a probar para determinar su primalidad.
7. Tacha el número 1.
8. Tacha los radios de los números primos como se encontró en el paso 1 y se aplicó en el paso 2 en todos los círculos exteriores sin tachar los números primos en el círculo más interno (en el círculo 1).
9. Tacha los radios de todos los múltiplos de números primos tachados del círculo interior 1 en el paso 4 de la misma manera que tachas los radios de los primos base en el paso 8.
10. Los números restantes en la rueda son en su mayoría primos (se les denomina colectivamente primos "relativamente"). Utilice otros métodos, como la criba de Eratóstenes o la aplicación de ruedas de factorización más grandes, para eliminar los números no primos restantes.

Nótese que al usar exactamente el siguiente número primo de 5 ciclos de rueda y eliminar los múltiplos de ese primo (y solo ese primo) de la lista resultante, hemos obtenido la rueda base según el paso 4 para una rueda de factorización con primos base de 2, 3 y 5; esta es una rueda por delante de la rueda de factorización {2,3} anterior. Luego se podrían seguir los pasos hasta el paso 10 usando el siguiente primo de 7 ciclos y eliminando solo los múltiplos de 7 de la lista resultante en el paso 10 (dejando algunos primos "relativos" en este caso y en todos los casos sucesivos, es decir, algunos primos que no son realmente primos completamente calificados), para obtener la siguiente rueda más avanzada, repitiendo recursivamente los pasos según sea necesario para obtener ruedas sucesivamente más grandes.

Formalmente, el método se basa en las siguientes ideas: primero, que el conjunto de primos base unido a su conjunto (infinito) de coprimos es un superconjunto de los primos; segundo, que el conjunto infinito de coprimos se puede enumerar fácilmente desde los coprimos hasta el conjunto base entre 2 y el producto del conjunto base. (Nótese que 1 requiere un tratamiento especial).

Como se ve en el ejemplo anterior, el resultado de aplicaciones repetidas del procedimiento recursivo anterior desde los pasos 4 al 10 puede ser una lista de rueda que abarca cualquier rango de tamizado deseado (al que se puede truncar) y la lista resultante incluye entonces solo los múltiplos de primos mayores que uno más allá de los primos base utilizados por última vez.

Una vez que una rueda abarca el límite superior deseado del rango de cribado, se puede dejar de generar más ruedas y usar la información de esa rueda para descartar los números compuestos restantes de esa última lista de ruedas usando una técnica tipo Criba de Eratóstenes, pero usando el patrón de huecos inherente a la rueda para evitar descartes redundantes; se pueden hacer algunas optimizaciones basándose en el hecho de que (se demostrará en la siguiente sección) no habrá descarte repetido de ningún número compuesto: cada compuesto restante se descartará exactamente una vez. Alternativamente, se puede continuar generando listas de ruedas truncadas usando primos hasta la raíz cuadrada del rango de cribado deseado, en cuyo caso todas las representaciones numéricas restantes en la rueda serán primas; sin embargo, aunque este método es tan eficiente como para no descartar nunca números compuestos más de una vez, pierde mucho tiempo fuera de las operaciones de descarte consideradas normalmente en el procesamiento de los sucesivos barridos de la rueda, por lo que toma mucho más tiempo. La eliminación de números compuestos mediante una rueda de factorización se basa en lo siguiente: dado un número k > n , sabemos que k no es primo si k mod n y n no son primos entre sí. A partir de esto, se puede determinar la fracción de números que elimina la criba (aunque no es necesario eliminarlos físicamente; muchos se pueden descartar automáticamente en las operaciones de copia de ruedas menores a ruedas mayores) como 1 − φ ( n ) / n , que también es la eficiencia de la criba.

Se sabe que

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }\sim 0.56145948,}$

donde γ es la constante de Euler . ^{[ 5 ]} Por lo tanto, φ ( n ) / n tiende a cero lentamente a medida que n aumenta hasta el infinito, y se puede observar que esta eficiencia aumenta muy lentamente hasta el 100% para n infinitamente grande . A partir de las propiedades de φ , se puede ver fácilmente que el tamiz más eficiente menor que x es aquel donde n = p ₁ p ₂ … p _i < x y np _{i +1} ≥ x (es decir, la generación de ruedas puede detenerse cuando la última rueda pasa o tiene una circunferencia suficiente para incluir el número más alto en el rango de tamizado).

Para que sea de máxima utilidad en un ordenador, queremos que los números menores que n y coprimos con él formen un conjunto. Con unas pocas observaciones, este conjunto se puede generar fácilmente:

1. Comencemos con S ₁ = {1} , que es el conjunto para n = 1 con 2 como el primer primo. Este conjunto inicial significa que todos los números a partir del dos están incluidos como primos "relativos" ya que la circunferencia de la rueda es 1.
2. Los siguientes conjuntos son S ₂ = {1} , lo que significa que comienza en 3 para todos los números impares con los factores de 2 eliminados (circunferencia de 2), S ₆ = {1,5} tiene los factores de 2 y 3 eliminados (circunferencia de 6) como para la rueda base inicial en el ejemplo anterior, y así sucesivamente.
3. Sea S _n + k el conjunto donde k se ha añadido a cada elemento de S _n .
4. Entonces S _{np i +1} = F _{p i +1} [ S _n ∪ S _n + n ∪ S _n + 2 n ∪ … ∪ S _n + n ( p _{i +1} − 1)] , donde F _x representa la operación de eliminar todos los múltiplos de x .
5. 1 y p _{i +1} serán los dos más pequeños de S _n cuando n > 2 , eliminando la necesidad de calcular los números primos por separado, aunque el algoritmo necesita mantener un registro de todos los primos base eliminados que ya no están incluidos en los conjuntos subsiguientes.
6. Todos los conjuntos cuya circunferencia n > 2 son simétricos respecto a n / 2 , lo que reduce los requisitos de almacenamiento. El siguiente algoritmo no utiliza este hecho, pero se basa en que los intervalos entre números sucesivos en cada conjunto son simétricos respecto al punto medio.

• Tamiz de Sundaram
• Tamiz de Atkin
• Tamiz de Pritchard
• Teoría del tamiz

• Factorización de ruedas
• Cribas incrementales mejoradas para números primos por Paul Pritchard
• Código de números primos