Múltiplos de números primos < números naturales VS Múltiplos de números impares < números naturales

Question

Al tomar un conjunto de números consecutivos debemos tener en cuenta que existen múltiplos de números primos que comprometen a la mayoría de los números:

0,5 de todos los números serán múltiplos de 2

0,333333 de todos los números serán múltiplos de 3, sin embargo 0,5 de éstos serán también múltiplos de 2 y por lo tanto sólo 0,16666666 serán múltiplos de sólo 3

0.2 de todos los números serán múltiplos de 5, sin embargo 0.3333333333333333 de estos serán también múltiplos de 3 y por lo tanto sólo 0.1333333333333 serán múltiplos de 5, sin embargo 0.5 de estos serán también múltiplos de 2 y por lo tanto sólo 0.06666666666666666 serán múltiplos de sólo 5

y así sucesivamente ....

Como puedes ver aquí: http://numbersprime.com/newtz.php el total parece no sumar nunca 1, lo que significa que siempre habrá un porcentaje de números que sean múltiplos de primos inferior al 100%, lo que lleva al hecho de que los demás números deben ser primos

Sin embargo en mi experimento, tomo todos los múltiplos de 2 y todos los múltiplos de todos los números Impares (no sólo números primos) y como se puede ver aquí: http://numbersprime.com/newtz2.php parece que el total nunca sumará 1, lo que lleva al hecho de que los otros números deben ser primos.

Dado que mi capacidad de cálculo tiene límites, como puede verse en los enlaces anteriores, me preguntaba si cabe esperar que el total sea siempre inferior a 1.

Answer 1

Parece que está construyendo el Tamiz de Eratóstenes .

Esta es una forma eficiente de generar una lista de primos. Primero se escriben los números naturales empezando por $2$ y hasta donde le permitan su papel y lápiz (u ordenador) ( $30$ en mi caso).

$2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30$

Ahora tacha todos los múltiplos de $2$ excepto $2$ sí mismo.

$\require{cancel} 2, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, 9, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, 15, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, 21, \cancel{22}, 23, \cancel{24}, 25, \cancel{26}, 27, \cancel{28}, 29, \cancel{30}$

Ingenuamente, casi la mitad de los números han desaparecido.

Ahora tacha todos los múltiplos de $3$ excepto $3$ (que no estén ya tachados).

$\require{cancel} 2, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \cancel{21}, \cancel{22}, 23, \cancel{24}, 25, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}$

Ahora, casi un tercio de los números restantes han desaparecido.

Y ahora $5$ ,

$\require{cancel} 2, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \cancel{21}, \cancel{22}, 23, \cancel{24}, \cancel{25}, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}$

$8$ de $30$ queda, esto es conveniente, ver más abajo.

Etc.

Lo que queda, son los primos hasta el cuadrado de tu último número inicial. Después de eso, también tendrá no-primos cuyos factores son todos mayores que su último tachado.

Por tanto, si en cada etapa tachas el propio número, sólo tendrás números primos mayores que el último que hayas tachado o números compuestos cuyos factores sean todos esos primos.

Digo ingenuamente por encima, ya que aunque, intuitivamente, la mitad de los números naturales son pares, se necesita algún esfuerzo para hacer una afirmación precisa. Densidad natural es una forma de hacerlo.

Más arriba digo que $8$ de $30$ era conveniente. Si quieres programar el tamiz, puedes aprovecharlo. En cada bloque consecutivo de $30$ números naturales (más allá de $30$ ), $22$ ciertamente no son primos. Por lo tanto, se puede registrar el primado de la $8$ candidatos utilizando un mapa de bits en un byte. De este modo, con $1$ GiB de memoria para su tamiz, podría generar una lista de primos hasta $8,000,000,000$ y un poco.