3
$\begingroup$

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.

  • 0
    Would you mind posting an answer?2013-05-21

0 Answers 0