This Question Maybe 21 Years Old

Algebra Level 3

Find the positive integer $n$ , for which $\lfloor \log_2{1}\rfloor+\lfloor\log_2{2}\rfloor+\lfloor\log_2{3}\rfloor+\cdots+\lfloor\log_2{n}\rfloor=1994.$

The answer is 312.

1 solution

Chew-Seong Cheong
Feb 15, 2015

Let $k = 2^i +j$ , where $i$ , $j$ and $k$ are non-negative integer and $j < 2^i$ then the $k^{th}$ term of the expression is:

$\quad a_k = \lfloor \log _2 {k} \rfloor = \lfloor \log _2 {(2^i+j)} \rfloor = i$

That is: $\quad \begin{array} {ll} \text{For } n = 1 & \Rightarrow a_k = 0 \\ \text{For } 2 \le n \le 3 & \Rightarrow a_k = 1 \\ \text{For } 4 \le n \le 7 & \Rightarrow a_k = 2 \\ \text{For } 8 \le n \le 15 & \Rightarrow a_k = 3 \\ & ... \end{array}$

Therefore,

$\displaystyle \quad \begin{aligned} S & = \lfloor \log _2 {1} \rfloor + \lfloor \log _2 {2} \rfloor + \lfloor \log _2 {3} \rfloor +...+ \lfloor \log _2 {n} \rfloor \\ & = \sum_{i=1} ^m {i(2^i)} = 1(2)+2(4)+3(8)+4(16)+5(32)+6(64)+7(128)+...\\ & = 2+8+24+64+160+384+896+... = 1538+8(j+1) = 1994 \end{aligned}$

$\Rightarrow j = \dfrac {1994-1538}{8} - 1 = 56$

Now, we know that the first $a_k = 8$ is when $i = 8$ and $k=2^8=256$

Therefore, $n = k+j = 2^i + j = 2^8+56 = 256+56=\boxed{312}$

Another way of finding the sum would be to consider the series $1 + x + {x}^{2} + {x}^{3}...{x}^{n} = \frac{{x}^{n+1}-1}{x-1}$ , differentiating it term-wise and then multiplying it by $x$ . After that, just substitute $x=2$ and Io, you have the same series get equaled to $(n-1)({2}^{n+1}) + 2$ .

Kartik Sharma - 6 years, 3 months ago

Thanks. I knew there should be a simpler way.

Chew-Seong Cheong - 6 years, 3 months ago

That's how i did it too.

Aakarshit Uppal - 6 years, 3 months ago

Well said.

Can also get to the expression

$(n-1)(2^{n+1})+2$

by noticing that we have a sum, in binary, of the form

$1...10 + 1...100 + 1...1000 + ... +10...0$

where each addend has the same number of digits, and that is equal to

$(2^{n+1}-2^2)+ (2^{n+1}-2^3)+ ...+(2^{n+1}-2^n) +2^{n+1} =(n-1)(2^{n+1})+2$

Peter Byers - 4 years, 9 months ago

This can also be generalized using the result from my solution on this problem.

Converting it into a double sum and evaluating it gives us a form and then a bit of analysis gives us the value of $n$ . First, we take the sum in LHS as $S$ . Now, we bound $n$ between two consecutive powers of $2$ . Let the power of $2$ which acts as the lower bound be $2^m$ for some non-negative $m$ . Then, we have,

$2^m\leq n\lt 2^{m+1}\implies \large S=\left(\sum_{k=0}^{m-1}\sum_{j=2^k}^{2^{k+1}-1}k\right)+\sum_{k=2^m}^nm$

From that solution I linked, we get that this evaluates to,

$\large S=(m-2)2^m+2+\sum_{k=2^m}^nm$

Now, comes the analysis part. Calculate $S$ for $n=2^7,2^8\textrm{ and }2^9$ with $m=7,8,9$ respectively (this agrees with the bounds). It becomes obvious that we need $m=8$ for the $S$ to equal $1994$ for some non-negative $n$ that satisfies our boundings. Then,

$S=1994\implies m=8\implies 1538+\sum_{k=256}^n8=1994\\ \implies (n-256+1)8=456\implies n-255=57\implies n=312$

Prasun Biswas - 6 years, 1 month ago

Almost had it :( .

Pawan pal - 5 years, 3 months ago

This Question Maybe 21 Years Old

The answer is 312.

1 solution

0 pending reports