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.

$\endgroup$
2
  • 5
    $\begingroup$ Bertrand's postulate gives the bound $n-2$. The prime number theorem can be used to show that for all $\epsilon>0$, the bound $\epsilon n$ will work for sufficiently large $n$. I'm not an expert and don't know how helpful this is, hence just a comment. Here's a reference: en.wikipedia.org/wiki/Bertrand%27s_postulate. Other results: $n/5$ works if $n\gt 24$, $n/16597$ works if $n\gt 2010760$, $n/(25\ln^2n)$ works if $n\gt 396738$. $\endgroup$
    – Jonas Meyer
    Commented Oct 31, 2010 at 8:07
  • 1
    $\begingroup$ I've posted a related question at MathOverflow: mathoverflow.net/questions/44466 $\endgroup$
    – Charles
    Commented Nov 1, 2010 at 21:22

2 Answers 2

Reset to default
7
$\begingroup$

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)$.

$\endgroup$
2
  • 3
    $\begingroup$ Baker-Harman-Pintz achieve O(n^(21/40)) which is almost as good as Cramer's conditional result you mention (but of course not as good as his conjecture). $\endgroup$
    – Charles
    Commented Nov 1, 2010 at 16:32
  • 2
    $\begingroup$ @Charles: nice. Do you want to update the Wikipedia article with that information? $\endgroup$
    – Qiaochu Yuan
    Commented Nov 1, 2010 at 17:12
2
$\begingroup$

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!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .