Why is $p_n \sim n\ln(n)$?

Question

I know that the prime number theorem states that the number of primes less than $x$ is approximately $\frac{x}{\ln(x)}$. However, why does this mean that $p_n \sim n\ln(n)$? (where $p_n$ is the $n$-th prime). If we replace $x$ with $p_n$ in the original equation, we have that $\pi(p_n) \ln({p_n})\sim p_n$, and $\pi(p_n)$ is just $n$, but what about the $\ln({p_n})$?

Answer 1

Made a jpeg, see if it comes out readable: Theorem 3 says that putting in the extra $\log \log n$ term is quite good.

Theorem 1. We have $$\frac{x}{\log x}\left(1 + \frac{1}{2 \log x}\right) < \pi(x)\qquad \text{for}\,59\leqq x, \tag{3.1}\label{3.1}$$ $$\pi(x) < \frac{x}{\log x}\left(1 + \frac{3}{2 \log x}\right) \qquad \text{for}\,1 < x. \tag{3.2}\label{3.2}$$ Theorem 2. We have $$x/(\log x - \tfrac{1}{2}) < \pi(x) \qquad\text{for}\,67 \leqq x, \tag{3.3}\label{3.3}$$ $$\pi(x) < x/(\log x - \tfrac{3}{2})\qquad \text{for}\,e^{3/2} < x$$ (and hence for $4.48169 \leqq x$).
Corollary 1. We have $$x/\log x < \pi(x) \qquad\text{for}\,17\leqq x, \tag{3.5}\label{3.5}$$ $$\pi(x) < 1.25506 x/\log x \qquad\text{for}\,1 < x. \tag{3.6}\label{3.6}$$ Corollary 2. For $1 < x < 113$ and for $113.6 \leqq x$ $$\pi(x) < 5x/(4 \log x). \tag{3.7}\label{3.7}$$ Corollary 3. We have $$3x/(5 \log x) < \pi(2x) - \pi(x) \qquad\text{for}\,20\tfrac{1}{2} \leqq x, \tag{3.8}\label{3.8}$$ $$0 < \pi(2x) - \pi(x) < 7x/(5 \log x) \qquad\text{for}\, 1 < x. \tag{3.9}\label{3.9}$$ For the ranges of $x$ for which these corollaries do not follow directly from the theorem, they can be verified by reference to Lehmer's table of primes [10]. A similar remark applies to all corollaries of this section unless a proof is indicated.

The inequality \eqref{3.8} improves a result of Finsler [3]. The left side of \eqref{3.9} is just the classic result, conjectured by Bertrand (and known as Bertrand's Postulate) and proved in Tchebichef [14], that therre is at least one prime between $x$ and $2x$. The right side of \eqref{3.9} gives a result of Finsler [3], with Finsler's integral $n$ replaced by our real $x$. Finsler's elementary proofs are reproduced in Trost [15] on p. 58. The relation \eqref{3.12} below states a result of Rosser [11].

Theorem 3. We have $$n(\log n + \log\log n - \tfrac{3}{2}) < p_n \qquad\text{for}\,2\leqq n, \tag{3.10}\label{3.10}$$ $$p_n < n(\log n + \log\log n - \tfrac{1}{2})\qquad\text{for}\,20\leqq n. \tag{3.11}\label{3.11}$$ Corollary. We have $$n \log n < p_n \qquad\text{for}\, 1 \leqq n, \tag{3.12}\label{3.12}$$ $$p_n < n(\log n + \log\log n)\qquad\text{for}\,6\leqq n. \tag{3.13}\label{3.13}$$

That looks pretty good. From https://projecteuclid.org/euclid.ijm/1255631807

Answer 2

An elementary proof. Let $p_n=k_n n \ln n.$ We have $$1\sim \frac {n-1}{n}=\frac {\pi (p_n)}{n}\sim \frac {p_n}{n\ln p_n}=$$ $$=\frac {k_n n\ln n}{n\ln k_n+n\ln n n+n\ln\ln n}=$$ $$=\frac {k_n}{\frac {\ln k_n}{\ln n}+1+\frac {\ln\ln n}{\ln n}}=^{def}W_n.$$

(1). When $k_n\ge 1$ we have $W_n= \frac {k_n}{o(k_n)+1+o(1)}.$ Since $W_n\sim 1$, this implies $ \lim\sup_{n\to\infty}k_n\le 1.$

(2a). If $|\ln k_n|=o(\ln n)$ then when $k_n<1$ we have $W_n=\frac {k_n}{1+o(1)},$ which, since $W_n\sim 1$ and $\lim\sup_{ n\to\infty}k_n\le 1$ from (1), implies $\lim\inf_{n\to\infty}k_n\ge 1.$

(2b).The other alternative $|\ln k_n|\ne o(\ln n)$ for $k_n<1$ would imply (since $\lim\sup_{n\to\infty}k_n\le 1$) that for some $c>0$ there are infinitely many $n$ for which $(-\ln k_n)=|\ln k_n|>c\ln n$ and hence $k_n<n^{-c}.$ But for such $n$ we would have $p_n=k_n n \ln n<n^{1-c}\ln n,$ and we have $\ln n<n^c$ for all sufficiently large $n,$ so we would have $p_n<n$ for some $n\ge 1$, which is absurd. So this alternative is impossible.

Remark. $W_n\sim 1$ is by itself insufficient to prove $k_n\to 1.$ We must, as in (2b), use the relation between $k_n$ and $p_n$ and the fact that $p_n>n. $

Answer 3

If viewed as an expectation

$\pi(n)=\frac{n}{\ln(n)}$

reads 'throw an event which has probability $\frac{1}{\ln n}$ $n$ times'.

So a number is prime with probability $\frac{1}{\ln n}$. So the expected number of throws to get a prime is $\ln n$.

So the $n^{th}$ prime expects $n\ln n$ throws.

Answer 4

First, we can prove the following statement:

Given two functions $f,g \colon \mathbb N \to \mathbb R$ such that $f(n) \sim g(n)$ and $g(n) \to \infty$, we have also $\ln(f(n)) \sim \ln(g(n))$.

Proof: By definition, $f(n) \sim g(n)$ means $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1$. Applying $\ln$ on both sides, we get

$$\ln\!\Big(\!\lim_{n\to\infty} \frac{f(n)}{g(n)}\!\Big) = \ln(1) = 0.$$

Due to the continuity of $\ln$, this is the same as

$$\lim_{n\to\infty} \ln\!\Big(\!\frac{f(n)}{g(n)}\!\Big) = 0,$$

which can be also written as

$$\lim_{n\to\infty} \big(\ln(f(n))-\ln(g(n))\big) = \lim_{n\to\infty} \ln(g(n))\Big(\frac{\ln(f(n))}{\ln(g(n))}-1\Big) = 0.$$

Since $g(n) \to \infty$, we have also $\ln(g(n)) \to \infty$, and therefore, the second factor of the product must necessarily converge to $0$:

$$\lim_{n\to\infty} \Big(\frac{\ln(f(n))}{\ln(g(n))}-1\Big) = 0.$$

But this is the same as

$$\lim_{n\to\infty} \frac{\ln(f(n))}{\ln(g(n))} = 1,$$ which means $\ln(f(n)) \sim \ln(g(n))$. $\tag*{$\blacksquare$}$

Now, we can apply the statement to $f(n) = \pi(n)$ and $g(n) = \frac n{\ln(n)}$:

$$\ln(\pi(n)) \sim \ln\!\Big(\!\frac n{\ln(n)}\!\Big) = \ln(n) - \ln(\ln(n)) \sim \ln(n), $$

where the last step can be checked very easily. Replacing $n$ by $p_n$, we get

$$\ln(\pi(p_n)) = \ln(n) \sim \ln(p_n),$$ and therefore, we finally have

$$p_n \sim n\ln(p_n) \sim n\ln(n).$$

Remark: Although the result is true, the fraction $\frac{n\ln(n)}{p_n}$ converges quite slowly to $1$. For example, if $n \approx 10^{10}$, the relative error is still about $8.7\%$. A much better approximation is

$$p_n \sim n \big(\ln(n)+\ln(\ln(n))-0.95\big),$$

where the corresponding relative error is about $0.01\%$.