Encontrar un número primo entre el $n$ $2n$

Question

Estoy tratando de encontrar un número primo entre el$n$$2n$.

Sé que el número de números primos entre $n$$2n$$n/(2\ln n)$.

Yo estaba pensando en elegir un número al azar entre el $n$ $2n$ y compruebe si su primo. Si no, repita.

Sin embargo, ¿cómo puedo encontrar las repeticiones necesarias para asegurarse de que encontrar un alojamiento con una probabilidad de .99?

Cualquier ayuda se agradece.

Answer 1

Su estimación para el número de números primos es falso: hay cerca de $$\frac{n}{\log n}$$ números primos entre $n$$2n$. Más específicamente, el número de $$n/\log n-kn/\log^2n+O(n/\log^3n)$$ donde $k=\log4-1=0.386\ldots.$

Aparte de eso, estás siendo esencialmente pidió el uso de la distribución geométrica aquí. Si su probabilidad de fracaso se $$ 1-\frac{1}{\log n} $$ entonces la probabilidad de error después de la $k$ ensayos $$ (1-\frac{1}{\log n})^k $$ y se puede resolver $$ (1-\frac{1}{\log n})^k=0.01 $$ tomando logaritmos.

Como un asunto práctico que se puede excluir, incluso los números de su búsqueda. En este caso, sus posibilidades de éxito por prueba de dobles y se puede resolver $$ (1-\frac{2}{\log n})^k=0.01 $$ en su lugar.

Answer 2

Su conjetura es conocido como el postulado de Bertrand:

Para cada $n > 1$ siempre hay al menos uno de los prime $p$ tal que $n < p < 2n$.

Demostrar la conjetura no es trivial, usted puede encontrar una prueba por Erdős en la Wikipedia. Él resultó aún más fuerte resultado que

... para cualquier entero positivo $k$, no es un número natural $N$ tal que para todos los $n > N$, hay, al menos, $k$ números primos entre $n$$2n$.

Answer 3

Por el Teorema de los números Primos, ${\pi(2n)}-{\pi(n)} \approx \frac{2n}{\ln(2n)}-\frac{n}{\ln(n)} \approx \frac{n}{2\ln(n)}$. Ahora que es bastante aproximado. Pero suponiendo que jugamos con sus reglas, la probabilidad de que nos vamos a encontrar con un primer si hemos elegido al azar un número entre el$n$$2n$$\frac{1}{2\ln(n)}$. Nos dicen que tenemos que ejecutar $r$ tales ensayos o repeticiones tales que la probabilidad de que haya al menos un primer en la búsqueda es $0.99$. Empleando la distribución binomial tenemos

$$\begin{align} 1-\left(1-\frac{1}{2\ln(n)} \right)^{r} &= 0.99 \\ \left(1-\frac{1}{2\ln(n)} \right)^{r} &= 0.01. \end{align}$$

La solución para $r$ rendimientos

$$ r=\log_{\left(1-\frac{1}{2\ln(n)}\right)}0.01=\frac{\ln(0.01)}{\ln\left(1-\frac{1}{2\ln(n)}\right)}.$$

El número de ensayos o repeticiones requeridas, tales que la probabilidad de que nos vamos a encontrar con un primer al menos una vez entre los $n$$2n$$\left\lceil \ln(0.01)/\ln\left(1-\frac{1}{2\ln(n)}\right)\right\rceil$.