Summation Closed form for floor$\left(\log_n\right)$

2,101

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$.

Share:
2,101

Author by

Dave Chen

Updated on August 01, 2022

• 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?