There is a result that if $p_n$ is the $n$th prime, then $p_n\sim n\log n$ as $n\rightarrow\infty$.

I wonder: Is it a direct consequence of the prime number theorem $\pi(x)\sim x/\log x$? The theorem says that there are approximately $n/\log n$ primes less than or equal to $n$. So there are approximately $n$ primes less than or equal to $n\log n$. So $p_n$ is approximately $n\log n$.

But I'm having trouble turning this into a formal argument. We have $\lim_{n\rightarrow\infty}\dfrac{\pi(n)\log n}{n}=1$. How would it show that $\lim_{n\rightarrow\infty}\dfrac{p_n}{n\log n}=1$?


The proposals are $p_n\sim n\log n$ and $\pi(x)\sim \frac{x}{\log x}$. Consider:

$$p_{\pi(x)}\sim \pi(x)\log\pi(x)\sim\frac{x}{\log x}\log\left(\frac{x}{\log x}\right)=\frac{x}{\log x}\left(\log x-\log\log x\right)\sim x$$


$$\pi(p_n)\sim\pi(n\log n)\sim\frac{n\log n}{\log(n\log n)}=\frac{n\log n}{\log n+\log\log n}\sim n$$

Try formailizing this (giving more meaning to $\sim$) to show that $p_{({.})}$ and $\pi({.})$ are asymptotic inverses.

To formalize more: Let $f(x)=\frac{x}{\log{x}}$ and $g(x)=x\log{x}$. Then $$\frac{f(g(x))}{x}=\frac{1}{x}\frac{x\log{x}}{\log(x\log{x})}=\frac{1}{1+\frac{\log\log x}{\log x}}\xrightarrow{x\to\infty}1$$

And $$\frac{g(f(x))}{x}=\frac{1}{x}\frac{x}{\log{x}}\log\left(\frac{x}{\log{x}}\right)=\frac{1-\frac{\log\log x}{\log x}}{1}\xrightarrow{x\to\infty}1$$

And so for large $x$, $f(g(x))\sim x$ and $g(f(x))\sim x$, where $A\sim B$ means that their ratio approaches $1$.

All this is to say that $f$ and $g$ are asymptotic inverses. So if we start with the premise that the $n$th prime number $p_n$ is approximately $g(n)$ (in the same "ratio approaches 1" sense), and then define $\pi(x)$ as the inverse concept (the number of primes less than a given $x$), then $\pi(x)$ is approximately $f(x)$ (again in that sense).

  • $\begingroup$ I added formalization. $\endgroup$ – alex.jordan Dec 17 '13 at 2:30

Continuing the argument, $n =\pi(p_n) \sim \frac{p_n}{\ln(p_n)}$.

If we can show that $\frac{\ln(p_n)}{\ln{n}} \to 1$, we can conclude that $p_n \sim n \ln n$.

This is a fairly direct consequence of $n \sim \frac{p_n}{\ln(p_n)}$.


Hint: By definition, $p_n=\inf\{x\mid\pi(x)\geqslant n\}$. For every $\varepsilon$ in $(0,1)$ there exists $x_\varepsilon$ such that $(1-\varepsilon)x/\log x\leqslant\pi(x)\leqslant(1+\varepsilon)x/\log x$ for every $x\geqslant x_\varepsilon$. Let $n_\varepsilon\geqslant(1+\varepsilon)x_\varepsilon/\log x_\varepsilon$, then, for every $n\geqslant n_\varepsilon$, ...

  • $\begingroup$ I'm following your argument. Could you tell me, for every $n\geq n_\varepsilon$, what you want there? I don't see what it should be. $\endgroup$ – PJ Miller Dec 14 '13 at 21:14
  • $\begingroup$ Obviously, what I am suggesting is that you do a part of the job yourself. Asking me to complete the argument is rather contradictory with this aim. Or, you will want to describe precisely which step you have a problem with. $\endgroup$ – Did Dec 15 '13 at 8:08
  • $\begingroup$ Sure, so for every $n\geq n_\epsilon$, we have $\pi(x_\epsilon)\leq(1+\epsilon)x_\epsilon/\log x_\epsilon\leq n_\epsilon\leq n$. Then I'm not sure how to continue. $\endgroup$ – PJ Miller Dec 15 '13 at 16:07

Note that $\pi(p_n)=n$ for all positive integers $n$ and $p_{\pi(q)}=q$ for all primes $q$. Thus

$$\lim_{n\to\infty}\left({n\log n\over p_n}\right)=\lim_{n\to\infty}\left({\pi(p_n)\log p_n\over p_n}\cdot{\log n\over\log p_n}\right)$$


$$\lim_{n\to\infty}\left({\pi(p_n)\log p_n\over p_n}\right)=\lim_{p\to\infty}\left({\pi(p)\log p\over p}\right)=1$$

is just the Prime Number Theorem. So it suffices to show that

$$\lim_{n\to\infty}\left({\log n\over\log p_n}\right)=1$$

Let's replace the sequence of integers $n$ with the sequence $\pi(q)$ where $q$ runs over the increasing sequence of primes. Using the relation $p_{\pi(q)}=q$, this gives

$$\lim_{n\to\infty}\left({\log n\over\log p_n}\right)=\lim_{q\to\infty}\left({\log\pi(q)\over\log q}\right)=\lim_{q\to\infty}\left({\log\left({\pi(q)\log q\over q}\right)+\log q-\log\log q\over\log q}\right)=1$$

where the final limit evaluation again makes use of the Prime Number Theorem, this time for $\log\left({\pi(q)\log q\over q}\right)\approx0$.

  • $\begingroup$ Beautiful. I think this will help the OP the most, as it's the cleanest argument and the first I understood all the way to the end. $\endgroup$ – ShreevatsaR Dec 17 '13 at 3:11
  • $\begingroup$ @ShreevatsaR, thank you! $\endgroup$ – Barry Cipra Dec 17 '13 at 3:12
  • $\begingroup$ BTW, in the very last "word", instead of $\log\left({\pi(q)\log q\over q}\right)\approx0$ I think you mean $\log\left({\pi(q)\log q\over q}\right)/\log q\to0$. $\endgroup$ – ShreevatsaR Dec 17 '13 at 3:13
  • $\begingroup$ @ShreevatsaR, no, you don't really need the log in the denominator. The Prime Number Theorem says that $\pi(q)\log q/q\approx1$, so its log is already close to $0$. $\endgroup$ – Barry Cipra Dec 17 '13 at 3:14
  • $\begingroup$ Oh yes... sure, that makes sense. $\endgroup$ – ShreevatsaR Dec 17 '13 at 3:15

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.