0
$\begingroup$

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

Thank you for your help.

Regards, Sandro

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, that's a good intuition. But how can I prove this formally? $\endgroup$ – S. M. Roch Aug 12 '16 at 16:43
  • $\begingroup$ "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. $\endgroup$ – fleablood Aug 12 '16 at 16:47
  • $\begingroup$ @S.M.Roch Prove what formally? $\endgroup$ – fleablood Aug 12 '16 at 16:49
  • $\begingroup$ 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. $\endgroup$ – S. M. Roch Aug 12 '16 at 17:39
0
$\begingroup$

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

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