# (AIME 1994) $\lfloor \log_2 1 \rfloor + \lfloor \log_2 2 \rfloor + \ldots + \lfloor \log_2 n \rfloor = 1994$

$$($$AIME $$1994)$$ Find the positive integer $$n$$ for which $$\lfloor \log_2 1 \rfloor + \lfloor \log_2 2 \rfloor + \lfloor \log_2 3 \rfloor + \ldots + \lfloor \log_2 n \rfloor = 1994$$ where $$\lfloor x \rfloor$$ denotes the greatest integer less than or equal to $$x$$.

The first few terms of this series shows me that summation $$\lfloor \log_2 n \rfloor$$ for $$n=1$$ to $$n=10$$ give $$2^{n +1}$$.

• Welcome to math.SE! Please show us your efforts on the question to avoid it being closed or heavily downvoted. For formatting help, See: Mathjax help page. For future reference, I would request you to read this page which will help you familiarize yourself with asking questions on this website. Thanks!
– Sil
Oct 28 '20 at 10:33
• Starting by writing down the first few values of each $\lfloor \log_2 n \rfloor$. Hint: it is related to the powers of $2$. (duh) Oct 28 '20 at 10:42
• Oct 29 '20 at 8:55

As noted, the sequence goes like

$$0,\underset{2}{\underbrace{1,1}},\underset{4}{\underbrace{2,2,2,2}},\underset{8}{\underbrace{3,3,3,3,3,3,3,3}},4,4,\ldots$$

i.e, every natural number $$k$$ occurs $$2^k$$ times.

So desired is $$\sum k\cdot 2^k =1994$$

It's quick enough to attack directly:

$$1\cdot2 + 2\cdot4 + 3\cdot8 + 4\cdot16 + 5\cdot 32 + 6\cdot 64 + 7\cdot 128 = 1538$$

Next up is $$8$$ repeating $$x$$ times till $$1994$$ $$1538 + 8\cdot x = 1994$$

$$\Rightarrow x=57$$

Last term of our sequence can be found by counting the number of repeating units: $$n = (1+2+4+\ldots+128) + 57 = \boxed{312}$$

Denote the sum by $$S_{n}$$. Note that for any $$k\in\mathbb{N}$$ there are $$2^k$$ positive integers $$x$$ for which $$[\log_{2}(x)]=k$$, and those are $$x=2^{k},2^{k}+1,\ldots,2^{k+1}-1$$. Thus we have $$S_{2^{k}-1}=0 + (1+1) + (2+2+2+2+) + \cdots + \bigl((k-1)+(k-1)+\cdots + (k-1)\bigr)$$ where there number of $$(k-1)$$ terms is $$2^{k-1}$$. It follows that $$S_{2^{k}-1} = (k-2)2^{k}+2$$ Putting $$k=8$$ we see that $$S_{255}=1538<1994$$ and putting $$k=9$$ we see that $$S_{511}=3586>1994$$. Thus it's clear that our $$n$$ should satisfy $$2^{8}-1. Now we have $$1994=S_{n}=S_{255}+(n-255)8=8n-502$$ which gives $$n=312$$.

We'll find a maximal $$m$$ for which $$\sum_{k=1}^mk2^k\leq1994.$$ Indeed, $$\sum_{k=1}^mk2^k=2\sum_{k=1}^mk2^{k-1}=2\left(\sum_{k=1}^mx^{k}\right)'_{x=2}=2\left(\frac{x(x^m-1)}{x-1}\right)'_{x=2}=$$ $$=2\cdot\frac{(m+1)2^m-1-2^{m+1}+2)}{(1-1)^2}=(m+1)2^{m+1}-2^{m+2}+2.$$ Id est, $$(m+1)2^{m+1}-2^{m+2}+2\leq1994,$$ which gives $$m=7$$.

Now, $$\frac{1994-((7+1)2^{7+1}-2^{7+2}+2)}{8}=57$$ and we obtain: $$n=1+2^1+...+2^7+57=2^8-1+57=312.$$

$$\lfloor \log_2 1 \rfloor + \lfloor \log_2 2 \rfloor + \lfloor \log_2 3 \rfloor + \ldots + \lfloor \log_2 n \rfloor = 1994$$

Let $$f(k)=\lfloor\log_2k\rfloor$$. Since $$\log$$ is increasing we know that

1. $$f(2^0)=f(1)=0$$
2. $$f(2^1)=f(2)=f(3)=1$$
3. $$f(2^2)=f(4)=f(5)=f(6)=f(7)=2$$
4. $$f(2^3)=f(8)=f(9)=\cdots=f(15)=3$$
5. $$f(2^4)=f(16)=f(17)=\cdots=f(31)=4$$
6. etc.

So there are 2 ones, 4 twos, 8 threes, 16 fours, 32 fives, 64 sixes, 128 sevens, 256 eights, etc. We can multiply these to form the sequence $$(2,8,24,64,160,384,896,2048)$$. Summing the first 7 terms of this sequence gives $$1538$$, so we're missing $$1994-1538=456$$. Since $$456/8=57<2048$$ then our $$n$$ should be $$2+4+8+16+32+64+128+57=311$$, but we must also account for the $$f(1)=0$$ term, so in fact $$n=312$$.