ampliación del 6n $\pm1$ regla principal para $30n$ , $210n$ ...

Question

Actualmente estoy creando un programa para buscar exhaustivamente números primos. Alguien me ha dicho que esta regla se puede ampliar multiplicando 6 por el siguiente número primo, lo que da 30, y luego continuar esta secuencia 210.

Los desplazamientos a partir de este valor serían los números primos menores que él, aparte de los que se multiplican entre sí para formar este valor, y también el 1.

Esto funciona para 30, lo que significa que los valores que tendrá que comprobar serían $30n+1$ , $30n+7$ , $30n+11$ , $30n+13$ , $30n+17$ , $30n+19$ , $30n+23$ y $30n+29$

Sin embargo, hay algo que falta para los valores más grandes, la persona que aprendí regla de dijo que había una manera de hacer que funcione para $210n$ y hacia arriba, sin embargo olvidaron cómo hacerlo.

Con un valor base de 210 hay que comprobar el 1, y todos los números primos inferiores a 210, sin incluir los factores primos de 210, como en el caso anterior. Sin embargo, también hay que comprobar $210n+121$ , $210n+143$ , $210n+169$ , $210n+187$ y $210n+209$ .

Alguna ayuda para averiguar cuales son las reglas para los otros valores a comprobar para valores mayores que $210n$ se agradecería mucho, ya que necesito calcularlos automáticamente para valores enormes de $n$ .

Answer 1

Construyamos el período $30$ secuencia de forma más instructiva, a partir del periodo $6$ secuencia.

El periodo $6$ se compone de $6n+1$ y $6n+5$ (este último equivale a $6n-1$ pero es más fácil utilizar sólo desplazamientos positivos). Esta secuencia evita todos los múltiplos de $2$ y todos los múltiplos de $3$ y observe que $6=2\cdot3$ .

El siguiente primo del que queremos evitar múltiplos es $5$ . Así que tome cinco períodos sucesivos de la $6$ -secuencia: $$1, 5\\7, 11\\13, 17\\19, 23\\25, 29$$ Cada columna tiene un múltiplo de $5$ en él, en este caso $5$ y $25$ . Una vez eliminados, nos queda el punto $30$ secuencia $30n+k$ donde $k\in\{1,7,11,13,17,19,23,29\}$ . Esta secuencia evita todos los múltiplos de $2$ , $3$ y $5$ .

Para ampliar esto con el siguiente primo, $7$ puedes hacer lo mismo. Toma $7$ períodos sucesivos de esta secuencia, deshacerse de los múltiplos de $7$ para darle la secuencia de periodo $210$ que evita todos los múltiplos de $2, 3, 5$ y $7$ .

$$1,7,11,13,17,19,23,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\\ 151,157,161,163,167,169,173,179\\ 181,187,191,193,197,199,203,209$$

De nuevo, cada columna tiene exactamente un múltiplo de $7$ en él ( $7$ , $49$ , $77$ , $91$ , $119$ , $133$ , $161$ , $203$ ). Elimínelos, y los restantes $49$ números de su periodo $210$ secuencia. Obsérvese que no todos son números primos, sino que también se incluyen productos de primos mayores que casualmente están por debajo de $210$ como $11^2=121$ y $11\cdot 19=209$ .

Este método pronto se vuelve difícil de manejar, ya que por cada primo adicional $p$ que desea evitar, el período se multiplica por $p$ y el número de casos a controlar en ese periodo se multiplica por $p-1$ .

En efecto, está generando el resultado de unas cuantas rondas del Tamiz de Eratóstenes pero, por lo general, es mejor utilizar el tamiz en su totalidad.