Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 http://stackoverflow.com/questions/4058172/tricky-algorithm-interview-question. Depending on the bound, the algorithm I come up with may or may not be deterministic.

share|improve this question
5  
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$. –  Jonas Meyer Oct 31 '10 at 8:07
1  
I've posted a related question at MathOverflow: mathoverflow.net/questions/44466 –  Charles Nov 1 '10 at 21:22

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
3  
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). –  Charles Nov 1 '10 at 16:32
2  
@Charles: nice. Do you want to update the Wikipedia article with that information? –  Qiaochu Yuan Nov 1 '10 at 17:12

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.