Floor Logs

Algebra Level 5

( ∑ N = 1 1024 ⌊ log ⁡ 2 N ⌋ ) m o d 1000 = ? \bigg ( \sum_{N = 1}^{1024} \lfloor \log_2 N \rfloor \bigg ) \bmod {1000} = \ ?


The answer is 204.

View wiki
Alex Wang by Alex Wang , 25, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Prasun Biswas
Apr 17, 2015

Let me do the honor of providing clarification (in response to the Challenge Master note on OP's solution) to this wonderful problem!

By the properties of logarithm and floor function, we have,

⌊ log ⁡ 2 N ⌋ = k ∣ 2 k ≤ N < 2 k + 1 , k ∈ Z 0 + ∀ N ∈ Z + \lfloor\log_2N\rfloor=k\mid 2^k\leq N\lt 2^{k+1}~,~k\in\Bbb{Z_0^+}~\forall~N\in\Bbb{Z^+}

Hence, the sum can be written compactly using double summation notation. Let the sum be S S . Then, we can write S S as,

S = ( ∑ k = 0 9 ∑ j = 2 k 2 k + 1 − 1 k ) + ⌊ log ⁡ 2 2 10 ⌋ \large S=\left(\sum_{k=0}^9\sum_{j=2^k}^{2^{k+1}-1}k\right)+\lfloor\log_22^{10}\rfloor

Now, the inner sum has a constant as its general term, so, for the evaluation of inner sum, we simply multiply the constant general term with the number of terms in inner sum. The number of terms in the inner sum is ( 2 k + 1 − 1 ) − 2 k + 1 = 2 k (2^{k+1}-1)-2^k+1=2^k . Hence,

S = ( ∑ k = 0 9 k ⋅ 2 k ) + 10 = ( ∑ k = 1 9 k ⋅ 2 k ) + 10 … ( i ) S=\left(\sum_{k=0}^9k\cdot 2^k\right)+10=\left(\sum_{k=1}^9k\cdot 2^k\right)+10\quad\ldots~(i)

We can ignore the k = 0 k=0 case of the sum since k ⋅ 2 k = 0 k\cdot 2^k=0 for k = 0 k=0 . Then,

2 S = ( ∑ k = 1 10 ( k − 1 ) 2 k ) + 20 … ( i i ) 2S=\left(\sum_{k=1}^{10}(k-1)2^k\right)+20\quad\ldots~(ii)

Subtract equation ( i ) (i) from ( i i ) (ii) to get,

S = 9 ⋅ 2 10 − ( ∑ k = 1 9 2 k ) + 10 = 8204 ≡ 204 ( m o d 1000 ) S=9\cdot 2^{10}-\left(\sum_{k=1}^92^k\right)+10=8204\equiv \boxed{204}\pmod{1000}

17 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

Great job! Can you generalize for the sum ∑ N = 1 2 M ⌊ log ⁡ 2 N ⌋ \displaystyle \sum_{N = 1}^{2^M} \lfloor \log_2 N \rfloor for positive integer M M ?

Here's the generalization:

As we did in the original solution, using the properties of logarithm and floor function, we can write the generalized sum as,

S = ∑ N = 1 2 M ⌊ log ⁡ 2 N ⌋ = ( ∑ k = 0 M − 1 ∑ j = 2 k 2 k + 1 − 1 k ) + ⌊ log ⁡ 2 2 M ⌋ , M ∈ Z + \large S=\sum_{N=1}^{2^M}\lfloor\log_2N\rfloor=\left(\sum_{k=0}^{M-1}\sum_{j=2^k}^{2^{k+1}-1}k\right)+\lfloor\log_22^M\rfloor~,~M\in\Bbb{Z^+}

The inner sum is evaluated using the same method used in the original solution. Evaluating the inner sum, we get,

S = ( ∑ k = 0 M − 1 k ⋅ 2 k ) + M ⟹ 2 S = ( ∑ k = 1 M ( k − 1 ) 2 k ) + 2 M ⟹ S = 2 S − S = ( M − 1 ) 2 M + ( ∑ k = 1 M − 1 ( k − 1 − k ) ⋅ 2 k ) + ( 2 M − M ) ⟹ S = ( M − 1 ) 2 M + M − ∑ k = 1 M − 1 2 k S=\left(\sum_{k=0}^{M-1}k\cdot 2^k\right)+M\implies 2S=\left(\sum_{k=1}^M(k-1)2^k\right)+2M\\ \implies S=2S-S=(M-1)2^M+\left(\sum_{k=1}^{M-1}(k-1-k)\cdot 2^k\right)+(2M-M)\\ \implies S=(M-1)2^M+M-\sum_{k=1}^{M-1}2^k

Using the formula for summation of a finite GP, we get,

S = ( M − 1 ) 2 M + M − ( 2 M − 2 ) = ( M − 2 ) 2 M + M + 2 S=(M-1)2^M+M-(2^M-2)=(M-2)2^M+M+2

Now, what we need is S m o d 1000 S\bmod 1000 . For smaller values of M M , this can be computed easily. But it becomes a problem when we're dealing with large values of M M . The main hurdle is to compute 2 M m o d 1000 2^M\bmod 1000 . Once we compute this, it becomes easy to compute the rest using elementary modular arithmetic manipulations. We can formulate the following algorithm that uses Euler's Theorem and Chinese Remainder Theorem for dealing with "large enough" M M :

∀ M ≥ 3 , 2 M ≡ { 0 ( m o d 8 ) 2 M m o d ϕ ( 125 ) ( m o d 125 ) ≡ { 0 ( m o d 8 ) 2 M m o d 100 ( m o d 125 ) \forall~M\geq 3~,~2^M\equiv\begin{cases}0\pmod8\\ 2^{M~\bmod~\phi(125)}\pmod{125}\end{cases}\equiv\begin{cases}0\pmod8\\ 2^{M~\bmod~100}\pmod{125}\end{cases}

Let a = 2 M m o d 100 ( m o d 125 ) a=2^{M~\bmod~100}\pmod{125} . Then, by the Chinese Remainder Theorem, our congruence system reduces to,

2 M ≡ 376 a ( m o d 1000 ) ⟹ S ≡ 376 ( M − 2 ) a + M + 2 ( m o d 1000 ) 2^M\equiv 376a\pmod{1000}\implies S\equiv 376(M-2)a+M+2\pmod{1000}

Now, computation of a a depends on the value of M M and can further be possibly generalized using numerical analysis but I think manual computation of a a simply using modular arithmetic manipulations is easy and hence, it doesn't need to be simplified further. So, we present our results as follows:

S m o d 1000 = { 1 , M = 1 4 , M = 2 ( 376 ( M − 2 ) a + M + 2 ) m o d 1000 ∀ M ≥ 3 S\bmod 1000=\begin{cases}1~,~M=1\\ 4~,~M=2\\ \left(376(M-2)a+M+2\right)\bmod{1000}~\forall~M\geq 3\end{cases}

where a = ( 2 M m o d 100 ) m o d 125 ∀ M ≥ 3 a=\left(2^{M~\bmod~100}\right)\bmod{125}~\forall~M\geq 3

Prasun Biswas - 6 years, 1 month ago

@Prasun Biswas , we really liked your comment, and have converted it into a solution. If you subscribe to this solution, you will receive notifications about future comments.

Brilliant Mathematics Staff - 6 years, 1 month ago
Alex Wang
Apr 15, 2015

The given sum is equal to S = ∑ k = 1 9 k 2 k + 10 = 1 ⋅ 2 1 + 2 ⋅ 2 2 + ⋯ + 9 ⋅ 2 9 + 10. S = \sum_{k = 1}^9 k2^k + 10 = 1 \cdot 2^1 + 2 \cdot 2^2 + \dots + 9 \cdot 2^9 + 10.

2 S = 1 ⋅ 2 2 + 2 ⋅ 2 3 + ⋯ + 9 ⋅ 2 10 + 20. 2S = 1 \cdot 2^2 + 2 \cdot 2^3 + \dots + 9 \cdot 2^{10} + 20.

Subtract these two equations, to get S = 9 ⋅ 2 10 − 2 9 − 2 8 − ⋯ − 2 2 − 2 1 + 10 = 8204 S = 9 \cdot 2^{10} - 2^9 - 2^8 - \dots - 2^2 - 2^1 + 10 = \boxed{8204}

3 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

It would have been better if you clarify how you converted the summation to ∑ k = 1 9 k 2 k + 10 \displaystyle \sum_{k=1}^9 k 2^k + 10 .

I typed this to calculator and got 8769....

Xi Huang - 6 years, 1 month ago

Log in to reply

Hmm check your work again.

Alex Wang - 6 years, 1 month ago
Chew-Seong Cheong
Apr 18, 2015

We note that:

∑ N = 1 2 M ⌊ log ⁡ 2 N ⌋ = ⌊ log ⁡ 2 1 ⌋ + ⌊ log ⁡ 2 2 ⌋ + ⌊ log ⁡ 2 3 ⌋ + ⌊ log ⁡ 2 4 ⌋ + . . . + ⌊ log ⁡ 2 2 M ⌋ = 0 + 1 + 1 + 2 + 2 + 2 + 2 + 8 ( 3 ) + 16 ( 4 ) + . . . . . . + 2 M − 2 ( M − 2 ) + 2 M − 1 ( M − 1 ) + M = ∑ N = 1 M − 1 2 N N + M \begin{aligned} \displaystyle \sum_{N=1}^{2^M} {\lfloor \log_2 {N} \rfloor} & = \lfloor \log_2 {1} \rfloor + \lfloor \log_2 {2} \rfloor + \lfloor \log_2 {3} \rfloor + \lfloor \log_2 {4} \rfloor +...+\lfloor \log_2 {2^M} \rfloor \\ & = 0 + 1 + 1 + 2 + 2 + 2 +2 + 8(3) + 16(4) + ... \\ & \quad \quad ... + 2^{M-2}(M-2)+ 2^{M-1}(M-1) + M \\ & = \displaystyle \sum_{N=1}^{M-1} {2^NN} + M \end{aligned}

Let us consider:

∑ N = 1 M − 1 N x N = ∑ N = 1 M − 1 ( N + 1 ) x N − ∑ N = 1 M − 1 x N = ∑ N = 0 M − 1 ( N + 1 ) x N − 1 − ∑ N = 0 M − 1 x N + 1 = d d x ∑ N = 0 M x N − x M − 1 x − 1 = d d x ( x M + 1 − 1 x − 1 ) − x M − 1 x − 1 = ( M + 1 ) x M x − 1 − x M + 1 − 1 ( x − 1 ) 2 − x M − 1 x − 1 \begin{aligned} \displaystyle \sum_{N=1}^{M-1} {Nx^N} & = \sum_{N=1}^{M-1} {(N+1) x^N} - \sum_{N=1}^{M-1} {x^N} \\ & = \sum_{N=0}^{M-1} {(N+1) x^N} - 1 - \sum_{N=0}^{M-1} {x^N} + 1 \\ & = \dfrac {d}{dx} \sum_{N=0}^{M} {x^N} - \dfrac {x^M-1}{x-1} = \dfrac {d}{dx} \left( \dfrac {x^{M+1}-1}{x-1} \right) - \dfrac {x^M-1}{x-1} \\ & = \dfrac {(M+1)x^M}{x-1} - \dfrac {x^{M+1}-1}{(x-1)^2} - \dfrac {x^M-1}{x-1} \end{aligned}

Now let x = 2 x=2

⇒ ∑ N = 1 M − 1 N x N = ∑ N = 1 M − 1 2 N N = ( M + 1 ) x M x − 1 − x M + 1 − 1 ( x − 1 ) 2 − x M − 1 x − 1 = ( M + 1 ) 2 M − 2 M + 1 + 1 − 2 M + 1 = ( M + 1 − 2 − 1 ) 2 M + 2 = ( M − 2 ) 2 M + 2 \begin{aligned} \Rightarrow \displaystyle \sum_{N=1}^{M-1} {Nx^N} & = \sum_{N=1}^{M-1} {2^NN} = \dfrac {(M+1)x^M}{x-1} - \dfrac {x^{M+1}-1}{(x-1)^2} - \dfrac {x^M-1}{x-1} \\ & = (M+1)2^M - 2^{M+1} + 1 - 2^M + 1 \\ & = (M+1-2-1)2^M +2 = (M-2)2^M+2 \end{aligned}

Therefore, ∑ N = 1 2 M ⌊ log ⁡ 2 N ⌋ = ( M − 2 ) 2 M + M + 2 \displaystyle \sum_{N=1}^{2^M} {\lfloor \log_2 {N} \rfloor} = (M-2)2^M+M+2

⇒ ∑ N = 1 2 10 ⌊ log ⁡ 2 N ⌋ = ( 10 − 2 ) 2 10 + 10 + 2 = 8204 \Rightarrow \displaystyle \sum_{N=1}^{2^{10}} {\lfloor \log_2 {N} \rfloor} = (10-2)2^{10}+10+2 = 8204

⇒ ( ∑ N = 1 2 10 ⌊ log ⁡ 2 N ⌋ ) m o d 1000 = 8204 m o d 1000 = 204 \Rightarrow \displaystyle \left( \sum_{N=1}^{2^{10}} {\lfloor \log_2 {N} \rfloor} \right) \mod{1000} = 8204 \mod{1000} = \boxed{204}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...