Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What asymptotic lower bounds are known on the number of primes between $n$ and $2n$, call it $\Pi(n) = \pi(2n)-\pi(n)$? Obviously Bertrand's Theorem is the statement that $\Pi(n) \geq 1$ for all $n$, and the PNT says that $\Pi(n) \approx \frac{n}{\log n}$ but doesn't provide a lower bound.

It seems like Hoheisel's result on prime gaps that there exists a $\theta \lt 1$ such that $\pi(x+x^\theta)-\pi(x) \approx \frac{x^\theta}{\log x}$ (as seen at ) should give a lower bound of the form $\Pi(n) \geq k\frac{n}{\log n}$ for some $k$ by stacking up $O(x^{1-\theta})$ such intervals; more precisely, if we take $c=2^{\theta}$ and $f(x) = x+x^\theta$, then since $x^\theta \leq cn^\theta$ for $x\leq 2n$, we have $f^{\circ t}(n) = f^{\circ(t-1)}(n) + \left(f^{\circ(t-1)}(n)\right)^\theta\leq f^{\circ(t-1)}(n) +cn^\theta\leq n+ctn^\theta$ as long as $ctn^\theta \lt n$ - or in other words, as long as $t\lt t_0 = c^{-1}n^{1-\theta}$, and therefore $$\begin{align*} \Pi(n) &= \pi(2n)-\pi(n) \\ &\geq \sum_{i=0}^{t_0-1} \left(\pi(f^{\circ (i+1)}(n))-\pi(f^{\circ i}(n))\right) \\ &\geq \sum_{i=0}^{t_0-1}\frac{(f^{\circ i}(n))^\theta}{\log f^{\circ i}(n)} \\ &\geq \sum_{i=0}^{t_0-1}\frac{n^\theta}{\log n} \\ &= t_0 \frac{n^\theta}{\log n} \\ &= c^{-1}\frac{n}{\log n} \end{align*}$$

Is this reasoning correct? It makes sense to me, but I'm surprised I've never seen such an explicit lower bound given before. While I'm more interested in the asymptotics, I'm also curious about the precise constants; if this is a known lower bound, is anything known about explicit $k$ such that $\Pi(n) \geq k\frac{n}{\log n}$ for all $n$ (or even all $n\gt n_0$)?

share|cite|improve this question
There are versions of the prime number theorem with bounds. Take a lower bound for $\pi(2n)$ and an upper bound on $\pi(n)$. – Hurkyl May 24 '12 at 18:09
@Hurkyl D'oh - of course, that's much easier than the path I went down and gives the same result. Feel free to give that as an answer! – Steven Stadnicki May 24 '12 at 18:31
up vote 6 down vote accepted

Quick and dirty bounds on the prime counting function are, for $n > 55$:

$$ \frac{n}{\log n + 2} < \pi(n) < \frac{n}{\log n - 4}, $$

and so you get the bounds

$$ \frac{2n}{\log(2n) + 2} - \frac{n}{\log n - 4} < \pi(2n) - \pi(n) < \frac{2n}{\log(2n) - 4} - \frac{n}{\log(n) + 2}. $$

Better bounds are available, but I find these simple enough that I prefer them when they are good enough for my purposes. From here, you should be able to massage them into whatever form you want (assuming you aren't looking for stronger approximations, of course).

share|cite|improve this answer

PNT says that $$\pi(2n) = 2n/\log(2n) + o(2n/\log 2n) = 2n/(\log n + \log 2) + o(2n/(\log n+\log 2)) = 2 (n/\log n) + o(n/\log n)$$ and that $\pi(n) = n/\log n + o(n/\log n).$ Putting these together gives $$\pi(2n) - \pi(n) = n/\log n + o(n/\log n ),$$ or equivalently, $$\pi(2n) - \pi(n) \sim n/\log n.$$

If you put in an actual bound for the error term in the prime number theorem, you can get an actual bound here as well. In any case, it shows that you can take $k$ as close to $1$ as you like, if $n$ is large enough.

share|cite|improve this answer

This problem is very closely related to Ramanujan primes, $R_n$:

$$\pi(x) - \pi(x/2) \ge n\text{ for all }x \ge R_n.$$

Clearly, by letting $x=2y$ we see that there are $n$ primes between $y$ and $2y$.

See And see the OEIS sequence A104272.

share|cite|improve this answer

Your Answer


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.