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

  • 1
    $\begingroup$ 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! $\endgroup$
    – Sil
    Oct 28 '20 at 10:33
  • $\begingroup$ 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) $\endgroup$
    – player3236
    Oct 28 '20 at 10:42
  • $\begingroup$ Related : math.stackexchange.com/questions/703895/… $\endgroup$
    – Arnaud D.
    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<n<2^{9}-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$.


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.