# Show that $n \sum\limits_{p \leq n} \frac{\log(p)}{p} = n \log(n) + \mathcal{O}(n)$

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.

-
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