Sum of floor logarithm function

Question

Given $$f(n) = \sum_1^n \lfloor \log_2 n \rfloor$$ Is there any non iterative function to simplify / get approximated value of $f(n)$, without involving absurdly big numbers (e.g. $n!$)

Answer 1

$\lfloor \log_2(1) \rfloor = 0$

$\lfloor \log_2(2) \rfloor = 1$

$\lfloor \log_2(3) \rfloor = 1$

$\lfloor \log_2(4) \rfloor = 2$

$\lfloor \log_2(5) \rfloor = 2$

$\lfloor \log_2(6) \rfloor = 2$

$\lfloor \log_2(7) \rfloor = 2$

In particular, notice that $f(3) = 2 \cdot 1$, $f(7) = f(3) + 4 \cdot 2$, $f(15) = f(7) + 8 \cdot 3$. So we get $f(2^k-1) = \sum\limits_{i=1}^{k-1} 2^i \cdot i$. But this is equal to $2^{k} k - 2^{k+1} + 2$ (which can be proved by induction).

This inspires the following. Let $k$ be a positive integer such that $ 2^{k+1}>n \geq 2^k$

Then $f(n) = f(2^k-1) + \sum\limits_{i=2^k}^n \lfloor \log_2(i) \rfloor = f(2^k-1) + (n - 2^k + 1) \cdot k = nk - 2^{k+1} +k+2 $

Also, notice that $k = \lfloor \log_2(n) \rfloor$ so this gives us a closed form for your sum in terms of $n$.