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]$?

  • 1
    $\begingroup$ $\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. $\endgroup$ – Arthur Jan 18 '16 at 14:26
  • $\begingroup$ 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 $\endgroup$ – 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).$

Your particular example is (up to offset) A094189, but I couldn't find more information about that case.

  • $\begingroup$ Can pi(n/10) be an upper bound for sufficiently large n? $\endgroup$ – ttt Jan 19 '16 at 14:48
  • $\begingroup$ I guess for n>=k , pi(n/10) is an upper bound $\endgroup$ – ttt Jan 19 '16 at 14:51
  • $\begingroup$ @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.$ $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Wojowu Jan 18 '16 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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