Number of Ones in the Binary Expansion!

Number Theory Level 5

S k = ∑ n = 1 ∞ F k ( n ) n ( n + 1 ) \Large{S_k = \sum_{n=1}^\infty \dfrac{F^k(n)}{n(n+1)} }

Let F ( n ) F(n) be the number of ones in the binary expansion of n n . For Example:

  • F ( 5 ) = F ( ( 101 ) 2 ) = 2 F(5) = F((101)_2) = 2
  • F ( 15 ) = F ( ( 1111 ) 2 ) = 4 F(15) = F((1111)_2) = 4

If S 1 S_1 can be represented as A ln ⁡ ( B ) A\ln(B) where A , B ∈ Z + A,B \in \mathbb Z^+ and B B isn't any perfect m t h m^{th} power of any integer with m ∈ Z , m ≥ 2 m \in \mathbb Z, \ m \geq 2 . Find the value of ( A − 8 ) ( B − 14 ) (A-8)(B-14) .

Note : F k ( n ) = ( F ( n ) ) k F^k(n) = (F(n))^k

Bonus : Generalize for S k S_k .


The answer is 72.

Satyajit Mohanty by Satyajit Mohanty , 24, India

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.

1 solution

Satyajit Mohanty
Aug 18, 2015

For any positive integer n n , denote the binary representation of n n by ∑ j = 0 ∞ z j ( n ) 2 j \displaystyle \sum_{j=0}^\infty z_j(n)2^j

Then F ( n ) = ∑ j = 0 ∞ z j ( n ) F(n) = \displaystyle \sum_{j=0}^\infty z_j(n) . Now:

S 1 = ∑ n = 1 ∞ F ( n ) n ( n + 1 ) = ∑ n = 1 ∞ ∑ j = 0 ∞ z j ( n ) n ( n + 1 ) = ∑ j = 0 ∞ ∑ n = 1 ∞ z j ( n ) n ( n + 1 ) S_1 = \displaystyle \sum_{n=1}^\infty \dfrac{F(n)}{n(n+1)} = \sum_{n=1}^\infty \sum_{j=0}^\infty \dfrac{z_j(n)}{n(n+1)} = \sum_{j=0}^\infty \sum_{n=1}^\infty \dfrac{z_j(n)}{n(n+1)}

= ∑ j = 0 ∞ ∑ v = 0 ∞ ∑ u = 0 2 j − 1 1 ( v 2 j + 1 + 2 j + u ) ( v 2 j + 1 + 2 j + u + 1 ) = \displaystyle \sum_{j=0}^\infty \sum_{v=0}^\infty \sum_{u=0}^{2^j - 1} \dfrac{1}{(v2^{j+1} + 2^j + u)(v2^{j+1} + 2^j + u+1)}

= ∑ j = 0 ∞ ∑ v = 0 ∞ ( 1 v 2 j + 1 + 2 j − 1 v 2 j + 1 + 2 j + 2 j ) = \displaystyle \sum_{j=0}^\infty \sum_{v=0}^\infty \left( \dfrac{1}{v2^{j+1} + 2^j} - \dfrac{1}{v2^{j+1} + 2^j + 2^j} \right)

= ∑ j = 0 ∞ ∑ v = 0 ∞ ( 1 2 j ( 2 v + 1 ) − 1 2 j ( 2 v + 2 ) ) = \displaystyle \sum_{j=0}^\infty \sum_{v=0}^\infty \left( \dfrac{1}{2^j(2v+1)} - \dfrac{1}{2^j(2v+2)} \right)

= ∑ j = 0 ∞ 1 2 j ∑ v = 0 ∞ ( 1 2 v + 1 − 1 2 v + 2 ) = ∑ j = 0 ∞ 1 2 j ∑ n = 1 ∞ ( − 1 ) n − 1 n = 2 ln ⁡ ( 2 ) = \displaystyle \sum_{j=0}^\infty \dfrac{1}{2^j} \sum_{v=0}^\infty \left( \dfrac{1}{2v+1} - \dfrac{1}{2v+2} \right) = \sum_{j=0}^\infty \dfrac{1}{2^j} \sum_{n=1}^\infty \dfrac{(-1)^{n-1}}{n} = \boxed{2\ln(2)}

∴ A = 2 , B = 2 , ( A − 8 ) ( B − 14 ) = ( 2 − 8 ) ( 2 − 14 ) = ( − 6 ) ( − 12 ) = 72 \therefore A=2, B=2, (A-8)(B-14) = (2-8)(2-14) = (-6)(-12) = \boxed{72}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...