2
$\begingroup$

Quoting from the Wikipedia article:

As a consequence of the prime number theorem, one gets an asymptotic expression for the $ n $th prime number, denoted by $ p_n $: $$ p_n \sim n \log n.$$

Can you explain how we get this approximate expression? I understand the number of prime numbers less than or equal to an integer $ N $, denoted as $ \pi(N) $ is approximately: $$ \pi(N) \sim \frac{N}{\log N}. $$

If the $ n $ prime number is approximately $ n \log n $, it implies that there are approximately $ n $ prime numbers less than or equal to $ n \log n $, i.e., $$ \pi(n \log n) \sim n. $$ But substituting $ N $ with $ n \log n $ in the formula of $\pi(N)$ we get $$ \pi(N) \sim \frac{N}{\log N} = \frac{n \log n}{\log (n \log n)} \not\sim n. $$ What am I doing wrong? How can I show that the statement quoted from Wikipedia is correct?

$\endgroup$
  • $\begingroup$ log(n log n) is very close to log(n). $\endgroup$ – Jalex Stark May 9 '18 at 3:24
1
$\begingroup$

$$\log(n\log n)=\log n+\log\log n=(1+o(1))\log n$$ therefore $$\frac{n\log n}{\log(n\log n)}=\frac{n\log n}{(1+o(1))\log n} =\frac{n}{(1+o(1))}\sim n.$$

$\endgroup$
0
$\begingroup$

It seems you are very new to prime number theory hence I am not sure if you understand the little $o$ notations. Hence I present @Lord Shark's answer in layman's terms.

$$ \log (n\log n) = \log n + \log\log n $$

But $\log\log n$ is exponentially smaller compared to $\log n$ i.e. it can be ignore compared to $\log n$. Hence as an approximation, we have

$$ \log (n\log n) \sim \log n $$

With this approximation

$$ \pi (n\log n) \sim \frac{n\log n}{\log (n\log n)} \sim \frac{n\log n}{\log n} \sim n $$

The smallest values of $x$ for which $\pi(x) = n$ is $x = p_n$ hence we have

$$ \pi (p_n) = n \sim \pi(n\log n) $$

or $p_n \sim n\log n$.

$\endgroup$

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.