Summation Closed form for floor$\left(\log_n\right)$
Suppose you want to calculate $$\sum_{i=1}^n \lfloor\log_a i\rfloor $$ in an integer base $a$ (non-integer is similar but more complicated and needs care). For $a^m\leq i<a^{m+1}$ you have $\lfloor\log_a i\rfloor=m$. Then there are $a^{m}(a-1)$ integers involved in this interval. Suppose $a^N\leq n<a^{N+1}$, i.e. $N=\lfloor\log_a n\rfloor$. Then $$ \sum_{i=1}^n \lfloor\log_a i\rfloor=N(n-a^N+1)+(a-1)\sum_{j=0}^{N-1} ja^j $$ The sum is calculated as $$ \sum_{j=0}^{N-1} ja^j=\frac{a}{(a-1)^2}-\frac{a^{N+1}}{(a-1)^2}+\frac{Na^N}{a-1} $$ So $$ \sum_{i=1}^n \lfloor\log_a i\rfloor=\lfloor\log_a n\rfloor(n+1)+ \frac{a}{a-1}-\frac{a^{\lfloor\log_a n\rfloor+1}}{a-1} $$ which reduces to you expression for $a=2$.
Related videos on Youtube
Comments
-
Dave Chen over 1 year
The closed sum for the floors of logs of consecutive integers is:
$$\sum_{i=0}^n \lfloor \log_2i\rfloor = n\lfloor \log_2n\rfloor-2^{\lfloor \log_2n\rfloor+1}+\lfloor \log_2n\rfloor+2$$
This formula works for $\log_2$, but I'm not sure how to adapt this to work for all bases.
I tried executing this and as you can see it works for base 2:
<?php $sum = 0; $n = 200; $base = 2; for ($i = 1; $i <= $n; $i++) $sum += floor(log($i, $base)); echo $sum . "\n"; echo $n * floor(log($n, $base)) - pow($base, floor(log($n, $base)) + 1) + floor(log($n, $base)) + 2;
1153 1153
However, once I change the base, it no longer works.
What is the correct closed sum for floors of logs in any base?