0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.