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?


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$ – Thomas Andrews Jun 19 '15 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 '15 at 16:41
  • $\begingroup$ Okay, I see it, because the sum is finite. $\endgroup$ – StefanH Jun 19 '15 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 '15 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.