2
$\begingroup$

I saw in my textbook the following theorem: $\pi(n)\sim n⁄ \log n$

And it states the following corollary from this theorem: $p_n\sim n \log n$

I tried to think how they made that conclusion but to no avail. Can someone explain me, considering I've just started my first degree in CS?

$\endgroup$

1 Answer 1

3
$\begingroup$

The function $p_n$ is the inverse of the function $\pi$

And if we calculate $p_n(\pi(n))$ with the given approximations, we have $p_n(\pi(n))\approx \frac{n}{log(n)}\log(\frac{n}{log(n)})= \frac{n}{log(n)}(log(n)-log(log(n))\approx\frac{n}{log(n)}log(n)=n$

$\endgroup$
3
  • $\begingroup$ This is not a way to get $p_n$, but a justification that the formula is asymptotically right. $\endgroup$
    – Peter
    Dec 23, 2015 at 17:09
  • $\begingroup$ I don't understand why $p_n$ is a function rather than just the nth prime number? $\endgroup$ Dec 23, 2015 at 17:13
  • $\begingroup$ We can consider it to be a function which maps $n$ to the $n-th$ prime. And $\pi(n)$ determines $m$ with $p(m)=n$ $\endgroup$
    – Peter
    Dec 23, 2015 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .