1
$\begingroup$

What would be the generalized formula for sum of logarithmic series - $$\lfloor \log_2 1 \rfloor + \lfloor \log_2 2 \rfloor + \lfloor \log_2 3 \rfloor + ... + \lfloor \log_2 n \rfloor $$

which can be denoted as - $$\sum_{i=0}^{n} \lfloor \log_2 n \rfloor $$

One answer to the problem would be $$\log_2 (n!) $$ But this doesn't help much, since as the n grows larger and larger, computing factorial of n would be too difficult. Furthermore, applying logarithmic function on the result of factorial n would again bring down the value to a greater extent. Hence the resultant value should be of decent magnitude (Not too large). So i am expecting there should be different way to express the solution for this, which should be easier to calculate.

Could someone provide an helping hand?

$\endgroup$
  • 1
    $\begingroup$ The factorial doesn't take into account the rounding down to the nearest integer. $\endgroup$ – Taneli Huuskonen Jan 1 '18 at 10:11
3
$\begingroup$

The basic idea is to consider the relationship between $i$ and $k$ in the inequality $$k \le \log_2 i < k+1.$$ We know from the continuity (and monotonicity) of $\log_2 x$ on $x > 0$, that for a given $i > 0$, there is always an integer $k$ such that this inequality holds, and that this integer is unique. Geometrically, what we are doing is finding, for any given $x = i$, a horizontal "strip" of height exactly $1$ on the graph of $y = \log_2 x$ such that the corresponding $y$-value for $x = i$ falls inside this strip, and that this strip must be positioned such that the boundary falls on integer values.

What is this desired relationship? Well, we simply take the inverse function: $$2^k \le i < 2^{k+1}.$$ Therefore, for integers $$i \in \{2^k, 2^k + 1, 2^k + 2, \ldots, 2^{k+1} - 1\},$$ the value of $\log_2 i$ is at least $k$ and less than $k+1$. This amounts to the same thing as saying $$\lfloor \log_2 i \rfloor = k.$$ Consequently, we may partition the positive integers into the sets $$\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, \{8, 9, 10, 11, 12, 13, 14, 15 \}, \ldots,$$ and more formally, we have $$\mathbb Z = \bigcup_{k=0}^\infty A_k,$$ where $$A_k = \{2^k, \ldots, 2^{k+1} - 1\}.$$ We then also have, if $a_k \in A_k$, $$\lfloor \log_2 a_k \rfloor = k .$$ You should be able to take this and continue to find the desired sum.

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