# A trivial question about the $n^{\text{th}}$ prime number

I would like to ask for a little help about a very trivial question from the number theory.

If $p_{n}$ is the $n^{\text{th}}$ prime number in the ascending sequence of prime numbers, show that $$p_{n}\sim n \log(n).$$

I am pretty sure, we should use the prime number theorem, which says that $$\mathbb{P}(x) = \sum_{p\leq x}1 \sim \frac{x}{\log(x)}$$ where $p$ is a prime number.

I would be glad if someone could help me with the idea. Thanks in advance!

• The prime number theorem is far from trivial... However, it follows rather trivially from the prime number theorem, since $\sum_{p\leq p_n}1=n$. – Tomas Aug 13 '13 at 13:34
• Right! I am so stupid...it was absolutely obvious! Thank you very much :) – Lullaby Aug 13 '13 at 13:35

At the lowest level, this isn't a question about prime numbers at all; instead, it's a question about finding the inverse to the function $f(x) = \frac{x}{\log x}$. A classic method for (asymptotically) approximating inverses is bootstrapping: start with some reasonable guess, 'plug it in' to the functional equation (in some form) to get a better approximation, and continue until your approximation stops getting better (or you get enough terms).

In this case, we want to find a $g(n)$ such that $n = \frac{g(n)}{\log g(n)}$; rearranging this gives $g(n) = n\log g(n)$, which seems like a fine place to start the bootstrapping. A reasonable first guess is simply $g_0(n)=n$ (note that starting with a constant $g_0()$ would lead to a linear guess on the first iteration); plugging this in to the equation yields, successively:

$$g_1(n) = n\log g_0(n) = n\log n$$ $$g_2(n) = n\log g_1(n) = n\log(n\log n) = n(\log n+\log\log n)$$ $$g_3(n) = n\log\left(n\log n+n\log\log n\right) = n\log\left(n\log n\cdot\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\log\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\frac{\log\log n}{\log n}+o\left(\frac{\log\log n}{\log n}\right)\right)$$

In the case to hand, of course, there are error terms in the original approximation $\pi(n) = \frac{n}{\log n}$ that make the higher-order terms here less relevant, but a slightly more careful bootstrapping will show that the top-order $\theta(n\log n)$ term survives unscathed; the exact expression, as per Wikipedia, is:

$$\frac{p_n}{n} = \log n+\log\log n-1+O\left(\frac{\log\log n}{\log n}\right)$$

As Tomas noted: assuming

$$\sum_{p \leq x} 1 \sim \frac{x}{\log (x)}$$

and using that

$$\sum_{p \leq p_n} 1 = n$$

we can solve

$$\frac{p_n}{\log (p_n)} \sim n \implies p_n \sim n \log n$$

Edit Since there are some concerns about this last step, here I give a slightly clumsy derivation.

First we have that $p_n / \log p_n = n + o(n)$ from the prime number theorem.

Second we have that $$\frac{n \log n}{\log (n\log n)} = n ( 1 - \frac{\log\log n}{\log n + \log\log n}) = n + o(n)$$

Combining the two statements we have $$\frac{p_n}{\log p_n} = \frac{n\log n}{\log (n\log n)} + o(n) \tag{*}$$

Now consider the function $g:x\mapsto x / \log x$. Its derivative is $$g'(x) = \frac1{\log x} - \frac{1}{(\log x)^2}$$ which is positive if $x > e$. So over the domain $(e,\infty)$ the function is invertible, with range $(e,\infty)$.

Now, consider $g^{-1}( g(n\log n) + o(n))$. Since $g(n \log n / 2) < g(n\log n) + o(n) < g(2n \log n)$ for sufficiently large $n$, we have that in the relevant interval $$\frac{1}{2\log n} < g' < \frac{1}{\log n}$$ so that $$g^{-1}(g(n\log n) + o(n)) = n\log n + o(n\log n)$$

So applying $g^{-1}$ to both sides of (*) we get that $$p_n = n\log n + o(n\log n)$$ or $$p_n \sim n\log n$$

• Not quite: We get $p_n / \log(p_n) \sim n$, but we actually want to convert that to $p_n / \log(n) \sim n$: not that this is hard, but it needs a little more work. Right? – ShreevatsaR Aug 13 '13 at 14:10
• @ShreevatsaR: oops, that was a typo. And yes, the $\implies$ is meant to hide a little bit of work. :-) – Willie Wong Aug 13 '13 at 14:12
• I have to admit that I missed that, too. So maybe it's not that trivial. – Tomas Aug 13 '13 at 15:48