Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Using the fact that $\log(n!) = n \log(n) - n + \mathcal{O}(\log(n))$ I am asked to show that:

$$ n \sum_{p \leq n} \frac{\log(p)}{p} = n \log(n) + \mathcal{O}(n) $$

Prior to this result it was shown that:

$$ \log(n!) = \sum_{p \leq n} \left( [n/p] + [n/p^2] + [n/p^3] + \dots \right) \cdot \log(p)$$

It is immediate that:

$$ n \log(n) - n + \mathcal{O}(\log(n)) = \sum_{p \leq n} \left( [n/p] + [n/p^2] + [n/p^3] + \dots \right) \cdot \log(p) $$

The quantity $\left( [n/p] + [n/p^2] + [n/p^3] + \dots \right)$ is the highest power of $p$ dividing $n!$. Obviously I have to get a $1/p$ into the sum somehow but it isn't clear to me what should replace the expression inside the sum. Any help would be appreciated.

share|cite|improve this question
Please avoid using \displaystyle in titles. – Asaf Karagila Sep 2 '12 at 12:17
Does $[n/p]+[n/p^2]+\ldots \le \frac n{p-1}=\frac np+\frac n{p^2-p}$ help? – Hagen von Eitzen Sep 2 '12 at 12:30
@ Hagen. That inequality seems very helpful. But I am being slow, why is $[n/p] + [n/p^2] + \dots \leq \frac{n}{p-1}$?. Also, my apologies @Asaf - why should \displaystyle not be used in titles? – Jack Rousseau Sep 2 '12 at 12:38
It breaks the main page's structure, and it looks bad. Remember that the title is not only for this page, it appears in the list of active questions of the main page too. – Asaf Karagila Sep 2 '12 at 12:45
Ah, I was not aware. Fair enough. – Jack Rousseau Sep 2 '12 at 12:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.