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

Question

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

Answer 1

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

Answer 2

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<n<2^{9}-1$. Now we have $$1994=S_{n}=S_{255}+(n-255)8=8n-502$$ which gives $n=312$.

Answer 3

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

Answer 4

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