# an upper bound for number of primes in the interval $[n^2+n,n^2+2n]$

What is an upper bound for the number of primes in an interval of $n$ consecutive numbers?

What is an upper bound for the number of primes in the interval $[n^2+n,n^2+2n]$?

• $\left\lfloor \frac n2 \right\rfloor + 1$ is the simplest expression that gives a sharp bound in the general case, I would say. It has equality for all the intervals going from $\{2\}$, up to and including $\{2, 3, 4, 5, 6, 7, 8\}$, as well as the odd-length intervals $\{3\}, \{3, 4,5\}, \{3, 4, 5, 6, 7\}$, and it is strictly bigger than the true value for any other interval. – Arthur Jan 18 '16 at 14:26
• yes,but I need an upper bound for sufficiently large n.I can prove that 2pi(n) is one upper bound,but I need better bound – ttt Jan 18 '16 at 14:34

$n$ consecutive numbers can hold at most A023193$(n)$ primes as long as the first is greater than $n$. A023193$(n) < 2\pi(n)$ for large $n,$ so in any case there are at most $O(n/\log n).$
• @ttt: I don't think so; it should be more than $\pi(0.499n)$ infinitely often. With $x=10^9$ I find 24127792 which is much closer to $\pi(10^9/2)=26355867$ than to $\pi(10^9/10)=5761455.$ – Charles Jan 19 '16 at 15:32
According to the Prime-counting function $$\text{number of primes below natural }n = \pi(n) \approx \frac{n}{\ln n}$$ so you just want an approximation of $\pi(n^2+2n) - \pi(n^2+n)$: \begin{align} \pi(n^2+2n) - \pi(n^2+n) &\approx \frac{n^2+2n}{\ln (n^2+2n)} - \frac{n^2+n}{\ln (n^2+n)}\\ &\approx \lim_{n \to \infty} \left( \frac{n^2+2n}{\ln (n^2+2n)} - \frac{n^2+n}{\ln (n^2+n)} \right)\\ &= \frac{n \left(-2 \ln \left(\frac{1}{n}\right)-1\right)}{4 \ln ^2\left(\frac{1}{n}\right)} - \frac{3 \left(\ln \left(\frac{1}{n}\right)+1\right)}{8 \ln ^3\left(\frac{1}{n}\right)}+O\left(\frac{1}{n}\right)\\ & \approx \frac{n \left(2 \ln n-1\right)}{4 \ln ^2n} - \frac{3 \left(-\ln n+1\right)}{-8 \ln ^3n}\\ & = \frac{n \left(2 \ln n-1\right)}{4 \ln ^2n} - \frac{3 \left(\ln n-1\right)}{8 \ln ^3n} \end{align} For example, let $n = 1000$, now you want to calculate the number of primes $\in [1000\cdot 1001, 1000\cdot 1002] \equiv [1001000, 1002000]$ and that's approximately $$\frac{1000 \left(2 \ln 1000-1\right)}{4 \ln ^21000} - \frac{3 \left(\ln 1000-1\right)}{8 \ln ^31000} = 67.1365$$ while the real number is $$78649 - 78572 = 77$$ so that's an error of about $13$% with $n = 1000$. Note that you'll be able to obtain better approximations either developing the series at $\infty$ to greater orders of magnitude, either taking $n$ very large.
• Asymptotic behavior of primes, which PNT tells you about, doesn't have to imply behavior in short intervals like it does in your answer. Indeed, I believe it's consistent with PNT that there are no primes between $n^2+n$ and $n^2+2n$ for large $n$. – Wojowu Jan 18 '16 at 18:44