1
$\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$
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$
  • $\begingroup$ This is not a way to get $p_n$, but a justification that the formula is asymptotically right. $\endgroup$ – Peter Dec 23 '15 at 17:09
  • $\begingroup$ I don't understand why $p_n$ is a function rather than just the nth prime number? $\endgroup$ – TheLogicGuy Dec 23 '15 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 '15 at 17:14

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.