Let $p_n$ be the $n$th prime.

Could someone please help me with the steps between $\pi(n)\sim\dfrac{n}{\log(n)}$ and $n=\pi(p_n)$, to the statement $p_n\sim n\log(n\log(n))$?

  • 1
    $\begingroup$ In Hardy's number theory book, it's $p_n \sim n \log n,$ without the extra occurrence of log inside the outer log. I don't know if that makes a difference... $\endgroup$ – coffeemath May 21 '14 at 10:42
  • $\begingroup$ Not much of a difference for small $n$, I don't know for large $n$. $\endgroup$ – martin May 21 '14 at 11:01
  • $\begingroup$ I am trying to find that in Hardy's book - do you have a chapter ref? $\endgroup$ – martin May 21 '14 at 11:09
  • 1
    $\begingroup$ In Hardy's "The Theory of Numbers" (fourth edition) on page 9 Theorem 6 (of section 1.8) is a statement of the prime number theorem, that $\pi(x) \sim x/\log x.$ [It isn't proved there, but in Ch XXII is a proof). More to the point, a fairly simple passage from the prime number theorem to $p_n \sim n \log n$ is presented right after that on the rest of page 9 into page ten. Basically he shows the function inverse to $x/\log x$ is asymptotic to $x \log x.$ $\endgroup$ – coffeemath May 21 '14 at 11:29
  • $\begingroup$ Great - that you :) $\endgroup$ – martin May 21 '14 at 11:31

Here is a sketchy derivation.

Note that

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

so we just need to prove the simpler statement that $p_n \sim n \log n$.

The formulas

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


$$ \begin{align} n &\sim \frac{p_n}{\log p_n} \\ p_n &\sim n \log p_n \\ &\sim n \log(n \log p_n) \\ &\sim n (\log n + \log \log p_n) \\ &\sim n \log n \end{align}$$

  • $\begingroup$ Very clear - thank you! :) $\endgroup$ – martin May 21 '14 at 12:15
  • $\begingroup$ last steps resemble the back substitution method using to solve recurrences. i think as you discard the loglog part, you implicitly made the assumption that p_n does not grow crazy fast like e^(x^x) or smthing right? Then that assumption turns out to be true at the end. ok i see another thing, if we go substitute more, we get logn + loglogn + .. and hopefully after some point loglog..log(p_n) grows slower than logn and all of the stuff is just logn. $\endgroup$ – Ahmet Bilal Nov 3 '18 at 13:33

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.