Tamiz probabilístico de Eratóstenes

Question

Considere el siguiente algoritmo:

function Rand():
    return a uniformly random real between 0.0 and 1.0

function Sieve(n):

    assert(n >= 2)

    for i = 2 to n
        X[i] = true

    for i = 2 to n
        if (X[i])
            for j = i+1 to n
                if (Rand() < 1/i)
                    X[j] = false

    return X[n]

¿Cuál es la probabilidad de que Sieve(k) devuelva true en función de k ? ¿Cuál es el límite de esta probabilidad a medida que k llega al infinito (si es que lo tiene)?

Answer 1

Esto es difícil de hacer exactamente porque las probabilidades están correlacionadas: un pequeño número de "primos" pequeños llevará a más "primos" grandes, y viceversa. La respuesta en stackoverflow ignora estas correlaciones, pero se acerca bastante al valor de $k=1000$ ( $0.1227$ en lugar de $0.1199\pm0.0003$ determinado por la simulación informática), por lo que parece una aproximación razonable modelar las probabilidades como independientes.

Al hacerlo, se obtiene una recursión mucho más sencilla que la utilizada en la respuesta de stackoverflow: $k+1$ tiene exactamente las mismas posibilidades de ser marcado como "compuesto" que $k$ y si $k$ es "prime" tiene una oportunidad adicional durante el $k$ -ésima iteración, con probabilidad $1/k$ . Así, las probabilidades $p_k$ de $k$ siendo "primos" satisfacen la relación de recursión

$$p_{k+1}=p_k\left(1-\frac{p_k}k\right)\;.$$

Podemos reescribirlo como

$$p_{k+1}-p_k=-\frac{p_k^2}k$$

y aproximarla mediante una ecuación diferencial:

$$p'=-\frac{p^2}k\;,$$

cuya solución general es

$$p=\frac1{c + \log k}$$

con una constante arbitraria $c$ que se ve influenciado por los errores de aproximación para pequeños $k$ . Desde $p_{1000}\approx0.12$ obtenemos $c\approx1.43$ por lo que una buena aproximación viene dada por

$$p_k\approx\frac1{1.43+\log k}\;.$$

Aquí hay un gráfico de los valores hasta $p_{1000}$ que muestra una concordancia bastante satisfactoria (rojo: modelo, verde: simulaciones):

Así, el tamiz probabilístico se comporta asintóticamente como el tamiz primo real.