Límites en el espaciado de los números primos

Question

Supongamos que n es un número entero. ¿Qué tipo de límites no sabemos por qué cerca de la más cercana primer p > n?

Me gustaría especialmente agradezco una respuesta que me empuja en la dirección correcta de la prueba de una buena obligado por este sin mostrar la prueba completamente.

Contexto: me encontré con esto mientras se alcanza una solución para http://stackoverflow.com/questions/4058172/tricky-algorithm-interview-question. Dependiendo del obligado, el algoritmo que se me ocurren pueden o no ser determinista.

Answer 1

Hay muchas cosas que se sabe acerca de esto. La mayoría de los que creo que vienen de algo llamado el Teorema de los números Primos, que se puede leer en la wikipedia.

Algo que podría ser útil con respecto a tu pregunta son las fórmulas en esta sección:

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

Las pruebas para la mayoría de estos teoremas son realmente difíciles y requieren una gran cantidad de conocimientos de análisis, aunque, para ser advertido!

Answer 2

La palabra clave que desea es brecha principal . El mejor resultado incondicional que puedo ver en esa página parece ser$O(n^{3/4 + \epsilon})$ para cualquier$\epsilon > 0$. Con la hipótesis de Riemann obtienes$O(\sqrt{n} \log n)$, pero una famosa conjetura afirma que deberías ser mucho mejor, algo así como$O((\log n)^2)$.