Estimate of $n$th prime

Solution 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$$

and

$$\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).

Solution 2:

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)}$.

Solution 3:

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)$$

Now

$$\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$.

Solution 4:

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$, ...