5
$\begingroup$

Why is

$$ p_n\sim\sum_{k=1}^{n}\log(p_k) $$

where $p_n$ is the $n$th prime?

In addition, is it true that

$$ n\log\left(\dfrac{\sum_{k=1}^{n}\log(k)}{\log(\log(n))}\right) $$

is a better approximation for $p_n$ than $n\log(n)$?

$\endgroup$
  • $\begingroup$ Isn't it true for non-prime numbers as well? $\endgroup$ – barak manos Aug 2 '14 at 17:44
  • 3
    $\begingroup$ $p_n \sim n\log n$, so $\log p_k \sim \log k$, and $\sum_{k=1}^n \log k \sim n\log n$. $\endgroup$ – Daniel Fischer Aug 2 '14 at 17:46
  • $\begingroup$ Seems to me that if it is true for all $P_n$ primes, then it has to be true at least for their "neighbors". $\endgroup$ – barak manos Aug 2 '14 at 17:46
  • $\begingroup$ @DanielFischer Wouldn't $\log p_k \sim k\log k$ instead of just $\log k$? $\endgroup$ – Darth Geek Aug 2 '14 at 17:49
  • 3
    $\begingroup$ @DarthGeek $\log p_k \approx \log (k\log k) = \log k + \log \log k$, and the $\log\log k$ term is asymptotically negligible. $\endgroup$ – Daniel Fischer Aug 2 '14 at 17:51
8
$\begingroup$

For a quick qualitative answer, we note that by the prime number theorem $p_k \sim k\log k$, and hence we have $\log p_k \sim \log k + \log \log k \sim \log k$, and

$$\sum_{k=1}^n \log k \sim n \log n.$$

One has to do some work, however, to see that the summation of asymptotically equal terms leads in this case to asymptotically equal sums.

Probably more instructive is a summation by parts,

$$\begin{align} \sum_{k=1}^n \log p_k &= \sum_{m \leqslant p_n} \left(\pi(m) - \pi(m-1)\right)\log m\\ &= \pi(p_n)\log p_n - \sum_{m\leqslant p_n} \pi(m)\left(\log (m+1) - \log m\right)\\ &= n\log p_n - \sum_{m\leqslant p_n} \pi(m) \left(\frac{1}{m} + O\left(m^{-2}\right)\right)\\ &= n\log p_n - \sum_{m\leqslant p_n} \frac{\pi(m)}{m} + O(\log\log p_n)\\ &= n\log p_n + O\left(\frac{p_n}{\log p_n}\right), \end{align}$$

and the prime number theorem says that $n\log p_n \sim p_n$.

Regarding the addition, Raymond Manzoni reports in his answer to a question on bounds for $p_n$ that Pierre Dusart proved that

$$\begin{align} \frac{p_n}n &\leqslant \log n+\log (\log n) -1+\frac{\log (\log n)-2}{\log n}\quad\text{for}\ n\geqslant 688383,\\ \frac{p_n}n &\geqslant\log n+\log (\log n)-1+\frac{\log (\log n)-21/10}{\log n}\quad\text{for}\ n\geqslant 3. \end{align}$$

Since

$$\sum_{k=1}^n \log k = \int_1^n \log t\,dt + \sum_{k=2}^n \left(\log k - \int_{k-1}^k \log t\,dt\right) = n\log n - n + O(\log n),$$

we have

$$\begin{align} \log \left(\frac{\sum_{k=1}^n \log k}{\log \log n}\right) &= \log \left(\frac{n\log n - n + O(\log n)}{\log \log n}\right)\\ &= \log \left(n\frac{\log n - 1 + O\left(\frac{\log n}{n}\right)}{\log \log n}\right)\\ &= \log n + \log \left(\log n - 1 + O\left(\tfrac{\log n}{n}\right)\right) - \log \log \log n\\ &= \log n + \log \log n + O\left(\log \log \log n\right), \end{align}$$

which means it is indeed a better approximation than $n\log n$. However, a still better approximation, at least for large $n$, is

$$p_n \approx n \log \left(\sum_{k=1}^n \log k\right)$$

without dividing the argument of the logarithm by $\log \log n$. Or the even more accurate $p_n \approx n(\log n + \log \log n - 1 + o(1))$ which is simple enough to remember even when one hasn't Dusart's bounds handy to look up.

$\endgroup$
  • $\begingroup$ thank you for the detailed answer - this is much clearer - again, many thanks $\endgroup$ – martin Aug 2 '14 at 18:26
  • 1
    $\begingroup$ I only just saw the addition, I've added an answer to that too. $\endgroup$ – Daniel Fischer Aug 2 '14 at 20:59
  • $\begingroup$ Great - thanks for the complete answer :) $\endgroup$ – martin Aug 3 '14 at 3:10

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.