Any hints how to prove for $n \in \mathbb N$ $$ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1) $$ where $\mathbb P$ denotes the set of all primes? As for all primes $p > n$ we have $\lfloor n/p \rfloor = 0$, the sum is finite, i.e. if $p_1, \ldots, p_k$ are all primes $\le n$ we have $$ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \frac{1}{n} \sum_{i=1}^k \left\lfloor \frac{n}{p_i} \right\rfloor \log p_i = \frac{1}{n} \sum_{i=1}^k \log\left( p_i^{\lfloor n/p_i \rfloor}\right) = \frac{1}{n} \log\left( \prod_{i=1}^k p_i^{\lfloor n/p_i\rfloor} \right) $$ so I guess we should somehow show that $\log n^n \approx \log\left( \prod_{i=1}^k p_i^{\lfloor n/p_i\rfloor} \right)$, but I have no idea how to proceed, so any hints?


2 Answers 2


Consider that:

$$ n! = \prod_{p\leq n} p^{\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\ldots}$$ hence: $$ \log(n!) = \sum_{p\leq n}\left\lfloor\frac{n}{p}\right\rfloor \log p + \sum_{k\geq 2}\sum_{p\leq n}\left\lfloor\frac{n}{p^k}\right\rfloor \log p = \sum_{p\leq n}\left\lfloor\frac{n}{p}\right\rfloor \log p + O(n)$$ and the LHS can be estimated through Stirling's approximation.

  • $\begingroup$ The assertion that the second part is $O(n)$ requires an argument, but yes. :) $\endgroup$ Jun 19, 2015 at 16:33
  • $\begingroup$ I found that for $k \ge 2$ we have $\sum_{p \le n} \lfloor n / p^k \rfloor \log p \in O(n)$, but that the infinite sum over all $k \ge 2$ is in $O(n)$ I did not see, would you mind giving another hint? $\endgroup$
    – StefanH
    Jun 19, 2015 at 16:41
  • $\begingroup$ Okay, I see it, because the sum is finite. $\endgroup$
    – StefanH
    Jun 19, 2015 at 16:55

We have $$\frac{1}{n}\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor \log\left(p\right)=\sum_{p\leq n}\frac{\log\left(p\right)}{p}+O\left(\frac{1}{n}\sum_{p\leq n}\log\left(p\right)\right) $$ because $\left\lfloor \frac{n}{p}\right\rfloor =\frac{n}{p}+O\left(1\right) $ and by Mertens first theorem we have that $$\sum_{p\leq n}\frac{\log\left(p\right)}{p}=\log\left(n\right)+O\left(1\right) $$ and by PNT $$\sum_{p\leq n}\log\left(p\right)=O\left(n\right) $$ hence $$\frac{1}{n}\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor \log\left(p\right)=\log\left(n\right)+O\left(1\right). $$

  • 1
    $\begingroup$ Thanks for your answer too! $\endgroup$
    – StefanH
    Jun 19, 2015 at 17:05

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.