I would like to ask for a little help about a very trivial question from the number theory.

If $p_{n}$ is the $n^{\text{th}}$ prime number in the ascending sequence of prime numbers, show that $$p_{n}\sim n \log(n).$$

I am pretty sure, we should use the prime number theorem, which says that $$\mathbb{P}(x) = \sum_{p\leq x}1 \sim \frac{x}{\log(x)} $$ where $p$ is a prime number.

I would be glad if someone could help me with the idea. Thanks in advance!

  • 5
    $\begingroup$ The prime number theorem is far from trivial... However, it follows rather trivially from the prime number theorem, since $\sum_{p\leq p_n}1=n$. $\endgroup$ – Tomas Aug 13 '13 at 13:34
  • $\begingroup$ Right! I am so stupid...it was absolutely obvious! Thank you very much :) $\endgroup$ – Lullaby Aug 13 '13 at 13:35

At the lowest level, this isn't a question about prime numbers at all; instead, it's a question about finding the inverse to the function $f(x) = \frac{x}{\log x}$. A classic method for (asymptotically) approximating inverses is bootstrapping: start with some reasonable guess, 'plug it in' to the functional equation (in some form) to get a better approximation, and continue until your approximation stops getting better (or you get enough terms).

In this case, we want to find a $g(n)$ such that $n = \frac{g(n)}{\log g(n)}$; rearranging this gives $g(n) = n\log g(n)$, which seems like a fine place to start the bootstrapping. A reasonable first guess is simply $g_0(n)=n$ (note that starting with a constant $g_0()$ would lead to a linear guess on the first iteration); plugging this in to the equation yields, successively:

$$g_1(n) = n\log g_0(n) = n\log n$$ $$g_2(n) = n\log g_1(n) = n\log(n\log n) = n(\log n+\log\log n)$$ $$g_3(n) = n\log\left(n\log n+n\log\log n\right) = n\log\left(n\log n\cdot\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\log\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\frac{\log\log n}{\log n}+o\left(\frac{\log\log n}{\log n}\right)\right)$$

In the case to hand, of course, there are error terms in the original approximation $\pi(n) = \frac{n}{\log n}$ that make the higher-order terms here less relevant, but a slightly more careful bootstrapping will show that the top-order $\theta(n\log n)$ term survives unscathed; the exact expression, as per Wikipedia, is:

$$\frac{p_n}{n} = \log n+\log\log n-1+O\left(\frac{\log\log n}{\log n}\right)$$


As Tomas noted: assuming

$$ \sum_{p \leq x} 1 \sim \frac{x}{\log (x)} $$

and using that

$$ \sum_{p \leq p_n} 1 = n $$

we can solve

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

Edit Since there are some concerns about this last step, here I give a slightly clumsy derivation.

First we have that $p_n / \log p_n = n + o(n)$ from the prime number theorem.

Second we have that $$ \frac{n \log n}{\log (n\log n)} = n ( 1 - \frac{\log\log n}{\log n + \log\log n}) = n + o(n) $$

Combining the two statements we have $$ \frac{p_n}{\log p_n} = \frac{n\log n}{\log (n\log n)} + o(n) \tag{*}$$

Now consider the function $g:x\mapsto x / \log x$. Its derivative is $$ g'(x) = \frac1{\log x} - \frac{1}{(\log x)^2} $$ which is positive if $x > e$. So over the domain $(e,\infty)$ the function is invertible, with range $(e,\infty)$.

Now, consider $g^{-1}( g(n\log n) + o(n))$. Since $g(n \log n / 2) < g(n\log n) + o(n) < g(2n \log n)$ for sufficiently large $n$, we have that in the relevant interval $$\frac{1}{2\log n} < g' < \frac{1}{\log n}$$ so that $$ g^{-1}(g(n\log n) + o(n)) = n\log n + o(n\log n) $$

So applying $g^{-1}$ to both sides of (*) we get that $$ p_n = n\log n + o(n\log n)$$ or $$ p_n \sim n\log n$$

  • 1
    $\begingroup$ Not quite: We get $p_n / \log(p_n) \sim n$, but we actually want to convert that to $p_n / \log(n) \sim n$: not that this is hard, but it needs a little more work. Right? $\endgroup$ – ShreevatsaR Aug 13 '13 at 14:10
  • 1
    $\begingroup$ @ShreevatsaR: oops, that was a typo. And yes, the $\implies$ is meant to hide a little bit of work. :-) $\endgroup$ – Willie Wong Aug 13 '13 at 14:12
  • 1
    $\begingroup$ I have to admit that I missed that, too. So maybe it's not that trivial. $\endgroup$ – Tomas Aug 13 '13 at 15:48

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.