Summation of $\sum_{k=1}^{n}\left \lfloor \log _{m}k \right \rfloor$ and $\sum_{k=1}^{n}\left \lceil \log_{m}k\right \rceil$

Question

$$\sum_{k=1}^{n}\left \lfloor \log _{m}k \right \rfloor$$ $$\sum_{k=1}^{n}\left \lceil \log_{m}k\right \rceil$$ I found myself stuck trying to solve these two summations but i can't make any progress. Any ideas?

Answer 1

The key to the first problem is to observe that $\left\lfloor\log_mk\right\rfloor=\ell$ if and only if $\ell\le\log_mk<\ell+1$, which is true if and only if $m^\ell\le k<m^{\ell+1}$. There are $m^{\ell+1}-m^\ell=m^\ell(m-1)$ integers $k$ in this range, and each of them contributes $\ell$ to the sum, so if $m^{\ell+1}\le n$, this interval contributes $\ell(m-1)m^\ell$ to the total.

Let $L=\lfloor\log_mn\rfloor-1$; for $\ell=1,\ldots,L$ we have $m^{\ell+1}\le n$, so these intervals contribute a total of

$$(m-1)\sum_{\ell=1}^L\ell m^\ell\tag{1}$$

to the sum. This answer shows one way to derive a closed form for $(1)$. It then only remains to add the contribution of

$$\sum_{k=m^{L+1}}^n\lfloor\log_mk\rfloor=\left(n-m^{L+1}+1\right)\lfloor\log_mn\rfloor\;.$$

The second problem can be done similarly.