1994 AIME Problems/Problem 4

Problem

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$ (For real $x\,$ , $\lfloor x\rfloor\,$ is the greatest integer $\le x.\,$ )

Solution 1

Note that if $2^x \le a<2^{x+1}$ for some $x\in\mathbb{Z}$ , then $\lfloor\log_2{a}\rfloor=\log_2{2^{x}}=x$ .

Thus, there are $2^{x+1}-2^{x}=2^{x}$ integers $a$ such that $\lfloor\log_2{a}\rfloor=x$ . So the sum of $\lfloor\log_2{a}\rfloor$ for all such $a$ is $x\cdot2^x$ .

Let $k$ be the integer such that $2^k \le n<2^{k+1}$ . So for each integer $j<k$ , there are $2^j$ integers $a\le n$ such that $\lfloor\log_2{a}\rfloor=j$ , and there are $n-2^k+1$ such integers such that $\lfloor\log_2{a}\rfloor=k$ .

Therefore, $\lfloor\log_2{1}\rfloor+\lfloor\log_2{2}\rfloor+\lfloor\log_2{3}\rfloor+\cdots+\lfloor\log_2{n}\rfloor= \sum_{j=0}^{k-1}(j\cdot2^j) + k(n-2^k+1) = 1994$ .

Through computation: $\sum_{j=0}^{7}(j\cdot2^j)=1538<1994$ and $\sum_{j=0}^{8}(j\cdot2^j)=3586>1994$ . Thus, $k=8$ .

So, $\sum_{j=0}^{k-1}(j\cdot2^j) + k(n-2^k+1) = 1538+8(n-2^8+1)=1994 \Rightarrow n = \boxed{312}$ .

Alternatively, one could notice this is an arithmetico-geometric series and avoid a lot of computation.

Solution 2

For this solution, we notice that values between ranges of $2^n$ are the same. Let's look at these ranges and their total value. It is trivial to conclude $\log_2{1} = 0$ so we will not write that.

$\begin{array}{cc} Range of k & Expression (Total) \\ 2 \leq k < 2^{2} & 1 \cdot (2^{2} - 2) = 2 \\ 2^{2} \leq k < 2^{3} & 2 \cdot (2^{3} - 2^{2}) = 8 \\ 2^{3} \leq k < 2^{4} & 3 \cdot (2^{4} - 2^{3}) = 24 \\ 2^{4} \leq k < 2^{5} & 4 \cdot (2^{5} - 2^{4}) = 64 \\ 2^{5} \leq k < 2^{6} & 5 \cdot (2^{6} - 2^{5}) = 160 \\ 2^{6} \leq k < 2^{7} & 6 \cdot (2^{7} - 2^{6}) = 384 \\ 2^{7} \leq k < 2^{8} & 7 \cdot (2^{8} - 2^{7}) = 896 \end{array}$

Sum of the values up to $1$ less than $2^k$ is $1538$ . This seems close enough to our desired value of $1994$ as any additional groups would exceed $1994$ . The difference is $1996 - 1538 = 456$ . Since the next numbers of the sequence will always be 8 since $\lfloor \log_2{2^8 + n < 2^9} \rfloor = 8$ , we can just find the number of '8's, which is $\frac{456}{8} = 57$ . So there are exactly 57 integers in that range. The largest integer, which is $a$ , is equal to $2^8 + 56 = \boxed{312}$ . ~Totient4Breakfast

1994 AIME (Problems • Answer Key • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

1994 AIME Problems/Problem 4

Contents

Problem

Solution 1

Solution 2

See also