4
$\begingroup$

Suppose n is an integer. What kind of bounds do we know for how close the closest prime p > n will be?

I'd especially appreciate an answer that pushes me in the right direction of proving a good bound for this without showing the proof fully.

Context: I ran into this while coming up to a solution for https://stackoverflow.com/questions/4058172/tricky-algorithm-interview-question. Depending on the bound, the algorithm I come up with may or may not be deterministic.

  • 1
    I've posted a related question at MathOverflow: http://mathoverflow.net/questions/444662010-11-01

2 Answers 2

7

The keyword you want is prime gap. The best unconditional result I can see on that page appears to be $O(n^{3/4 + \epsilon})$ for any \epsilon > 0. With the Riemann hypothesis you get $O(\sqrt{n} \log n)$, but a famous conjecture asserts that you should be able to do considerably better, something like $O((\log n)^2)$.

  • 2
    @Charles: nice. Do you want to update the Wikipedia article with that information?2010-11-01
2

There are many things that are known about this. Most of which I believe come from something called the Prime Number Theorem, which you can read about on wikipedia.

Something that might be helpful with regards to your question are the formulas in this section:

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

The proofs for most of these theorems are really tricky and require a lot of knowledge of analysis though, so be warned!