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

Related videos on Youtube

Dave Chen
Author by

Dave Chen

Updated on August 01, 2022

Comments

  • Dave Chen
    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;
    

    Output:

    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?