# prime number theorem equivalence

Well, I'm far away of understanding the proof of the prime number theorem. But I have this stupid question:

How can I show this equivalence:

$\pi (x) \thicksim \frac{x}{ \log (x) } \iff p_n \thicksim n \cdot \log (n)$

Where $p_n$ is the n-th prime number and $\pi(x)$ is the prime number counting function, that means $\pi(x) = |\{n \in \mathbb{N} : (n \le x) \land (n \text{ is prime})\}|$

Regards, Sandro

The weak version of the PNT states that for any $x$ big enough $$\frac{c_1 x}{\log x}\leq \pi(x) \leq \frac{c_2 x}{\log x}$$ with $c_1<1<c_2$ and $c_1+c_2=2$. Since $\pi(p_n)=n$, it follows that $$\frac{c_1 p_n}{\log p_n} \leq n \leq \frac{c_2 n}{\log p_n}$$ hence $$c_1 p_n \leq n \log p_n \leq n\log\left(n\cdot\frac{\log p_n}{c_1}\right)=n\log(n)\left(1+o(1)\right)$$ and similarly $c_2 p_n = n\log n(1+o(1))$, hence $\pi(x)\sim\frac{x}{\log x}$ implies $p_n\sim n\log n$.
On the other hand, if we know that $\pi(n\log n)\sim n$, then $$\pi(m)\sim\frac{m}{W(m)}$$ where $W$ is the Lambert function, and for large values of $m$ we have $W(m)\sim \log(m)$ since $xe^x = e^{x+o(1)}$.

$$\pi(x) \sim x/\ln(x)$$ basically says that if you take the first $x$ integers and start iterating through them (starting at $1$) then roughly every $\ln(x)$ number you will find a prime number. This can also be seen as the probabilty of a particular number in $\{1,...,x\}$ to be prime is $1/\ln(x)$ since you know there are $\pi(x)$ prime number in this set and the size of the set is $x$ : $probability = good\_case/total\_case = \pi(x) / x \sim 1/\ln(x)$.

Therefore if you want to have the $n$'th prime number you will have to iterate through $n \ln(n)$ numbers before seening it.

• Yes, that's a good intuition. But how can I prove this formally? – S. M. Roch Aug 12 '16 at 16:43
• "then roughly every ln(x) number you will find a prime number" I'd quibble and say roughly on average the prime numbers are ln(x) apart as we know they are not evenly distributed. – fleablood Aug 12 '16 at 16:47
• @S.M.Roch Prove what formally? – fleablood Aug 12 '16 at 16:49
• I would like so see a proof that uses the definition $a_n \thicksim b_n :\iff \lim_{n \to \infty} \frac{a_n}{b_n} = 1$. Honestly, I'm not so familiar with the $\thicksim$ symbol. – S. M. Roch Aug 12 '16 at 17:39

$\pi(n) \approx n/\ln(n)$. That means of the numbers 1... $n$ roughly $1/\ln(n)$ are primes, or in other words primes occur on average $\ln (n)$ units apart. So $p_n$ being the $n$th prime is roughly $n*\ln(n)$.