Después de unos meses, hoy vuelvo a escribir, y sobre números primos.

Como todo lo que he escrito, empieza quizá hace una semana o dos atrás. Estoy, muy probablemente, en clases aburridas y recuerdo la criba de Eratóstenes y, general, algoritmos para la búsqueda de primos.

La criba de Eratóstenes consiste en una tabla desde 2 hasta n, cualquiera sea n mientras sea entero y positivo. Luego, empiezas a tachar todos los números divisibles por dos, luego empiezas a tachar todos los números por el número que siga al 2 que no esté tachado, 3, y así hasta tener solo números primos. El opuesto a la criba de Eratóstenes es el Trial Division, aplicar a todos los números desde 2 hasta donde se quiera el módulo de todos los primos menores a el de manera individual, dado que el módulo siempre da un resultado de 0 si n es divisible por p, podemos distinguir entre números compuestos y primos.

Trial Division

Dado el algoritmo de Trial Division, un par de modificaciones se hicieron. El algoritmo nuevo recorría en un bucle while todos los enteros de la forma 2k + 1, sabiendo que la parte entera de la mitad de un número de la forma 2k + 1 es k, se busca el primo más cercano a la mitad; ya que toda división de un n mayor a su mitad resulta en un número entre 1 y 2, esencialmente inútil. Entonces, se revisa de manera iterativa por el primalidad del número utilizando k módulo p. (Código fuente: kafka.py)

La siguiente modificación fue hecha un par de días antes y nuevamente reduce el tamaño del conjunto de búsqueda, hasta n = 100, siempre contienen un número primo. La idea viene de ver que para 2k + 1, dado un k = 3n + 1, 2k + 1 es múltiplo de 3. $$ 2(3n + 1) + 1 $$ $$ 6n + 2 + 1 $$ $$ \frac{6n + 3}{3} $$ $$ 3n + 1 $$ Antes de intentar generar una nueva fórmula para deshacerme de esos casos, primero reviso el recorrido de la función hasta k = 10, ignorando los casos ya descritos, por buscar algún patrón.

2	3	5	6	8	9
5	7	11	13	17	19

Lo primero que podemos ver es la diferencia de 4 entre cada par, ignorando múltiplos de 3. Dado que esta secuencia no puede ser generada de manera consistente, lo siguiente es hacer una secuencia. $$ B_0 = 5 $$ $$ B_n = \begin{cases} B_{n - 1} + 2, n \not\equiv 0 \pmod{2} \\ B_{n - 1} + 4, n \equiv 0 \pmod{2} \end{cases} $$

Con la secuencia definida, podemos ver que tanto se redujo el conjunto de búsqueda. Primero hay que definir r, que será número de terminos. Lo siguiente será dividir r por 6, y después de manera individual 2 y 3. De esa manera podemos obtener la cantidad de múltiplos de 2 menores a r y múltiplos de 3 menores a r, y restarles la intersección, o los múltiplos de 6. $$ r - ([\frac{r}{2} + \frac{r}{3}] - \frac{r}{6})$$ $$ r - (\frac{5r}{6} - \frac{r}{6}) $$ $$ r - \frac{4r}{6} $$ $$ \frac{r}{3} $$ Y tomando en cuenta que el número 1 jamás es probado, se le resta y redondea. $$ \lfloor \frac{r}{3} - 1 \rfloor $$

El procedimiento resulta en $\frac{r}{3} - 1$, de manera que hemos reducido el conjunto de números a buscar a un tercio. A largo plazo y de manera computacional, esto salva millones de llamadas y comparaciones. De manera práctica, esto resulta en comparaciones manuales de grupos más grandes en menos tiempo. Tomando r = 100, se hacen 32 revisiones, y se obtienen los primeros 25 números primos, contando al 2 y 3.

Aún después de tal reducción, la eficiencia del algoritmo deja mucho que desear. El algoritmo requiere de calcular módulos cada vez más grandes y más seguido.

Criba de Eratóstenes reducida

Se pueden extrapolar los resultados anteriores a la criba de Eratóstenes. Lo primero aplicado será el uso de una tabla con términos de la secuencia definida anteriormente. Dada la tabla, se hace la conjetura: dado cualquier n, si se avanzan kn pasos desde la casilla siguiente, o p + 1, la casilla es divisible por n.

En la imagen se tiene una tabla con los términos de la secuencia, y se marcan los primos y los múltiplos según la conjetura anterior. Finalmente, se eliminan todos los múltiplos de 5 que no hayan sido marcados, y esto nos deja los primeros 26 primos, sin contar al 2 y al 3.

Como observación final: sea p la posición en la tabla del término n, solo se necesita hacer el proceso de marcado para todo n tal que $ 2n + p \lt r $. Como desigualdad: $$ 2n + p \lt r $$ $$ 2n \lt r - p $$ $$ n \lt \frac{r - p}{2} $$

Si esa desigualdad no se cumple, no es necesario revisar n. Y, de manera más directa, para encontrar la máxima aproximada podemos razonar que, para cualquier máxima con posición mayor a 1, el resultado de $ \lceil \frac{r}{m} \rceil $ debe ser igual o mayor a 3.

$$ \lceil \frac{r}{m} \rceil \geq 3 $$

De manera alternativa:

$$ \frac{r}{m} \gt 2 $$ $$ r \gt 2m $$ $$ \frac{r}{2} \gt m $$

m siendo el último número en ser revisado. Para r = 35, como en el ejemplo del proceso de la criba reducida, nos da 35 / 2, lo cual es 17,5. Dado que la máxima tiene que ser menor, el número más cercano es 17, calzando perfectamente con la máxima que encontramos de manera práctica.

Conclusión

Se logra reducir la cantidad de números a revisar a $ \frac{r}{3} - 1 $ en Trial Division, y extrapolando los resultados a la criba de Eratóstenes, se reducen los números a buscar a todos los n menores a $ \frac{r}{2} $.

vis.svg
primes.txt