perplexus.info :: Just Math : Digital sum

Digital sum (Posted on 2005-08-20)

For each positive integer n, let A(n) be the number of digits in the binary representation of n, and let B(n) be the number of ones in the binary representation of n. What is the value of S:

S = (1/2)^[A(1)+B(1)] + (1/2)^[A(2)+B(2)] + (1/2)^[A(3)+B(3)] + ...

Submitted by pcbouhid

Rating: 4.4000 (5 votes)

Solution: (Hide)

One fact that we have to had in mind is that when we multiply an integer m by 2, in binary representation all we need to do is to add a zero (0) at the right.

So :

A(2n) = A(n) + 1 (since we add one digit), and
B(2n) = B(n), since the added digit was "0", not "1".

And, also :

A(2n+1) = A(n) + 1, and
B(2n+1) = B(n) + 1.

Thus, we have :

A(2n) + B(2n) = A(n) + B(n) + 1, and
A(2n+1) + B(2n+1) = A(n) + B(n) + 2.

We know that A(1) = 1 and B(1) = 1. So, the sum is :

S = (1/2)^2 + (1/2)^[A(2)+B(2)] + (1/2)^[A(3)+B(3)] + ...

A(2)+B(2) = A(1)+B(1)+1
A(3)+B(3) = A(1)+B(1)+2

A(4)+B(4) = A(2)+B(2)+1
A(5)+B(5) = A(2)+B(2)+2

A(6)+B(6) = A(3)+B(3)+1
A(7)+B(7) = A(3)+B(3)+2

and so on.

For the the first two sums, we have:

(1/2)^(A(2)+B(2)) + (1/2)^(A(3)+B(3)) =
=(1/2)^(A(1)+B(1)+1) + (1/2)^(A(1)+B(1)+2) =
=(1/2)*(1/2)^(A(1)+B(1) + (1/2^2)*(1/2)*(A(1)+B(1) =
=(1/2)^(A(1)+B(1))*[(1/2 + 1/4)] =
= 3/4 * 1/2^(A(1)+B(1))

For the next two, we have :

(1/2)^(A(4)+B(4)) + (1/2)^(A(5)+B(5)) =
=(1/2)^(A(2)+B(2)+1) + (1/2)^(A(2)+B(2)+2) =
=(1/2)*(1/2)^(A(2)+B(2) + (1/2^2)*(1/2)*(A(2)+B(2) =
=(1/2)^(A(2)+B(2))*[(1/2 + 1/4)] =
= 3/4 * 1/2^(A(2)+B(2))

For the next two terms, we have :

(1/2)^(A(6)+B(6)) + (1/2)^(A(7)+B(7)) =
=(1/2)^(A(3)+B(3)+1) + (1/2)^(A(3)+B(3)+2) =
=(1/2)*(1/2)^(A(3)+B(3) + (1/2^2)*(1/2)*(A(3)+B(3) =
=(1/2)^(A(3)+B(3))*[(1/2 + 1/4)] =
= 3/4 * 1/2^(A(3)+B(3))

And so on...

Thus :

S = 1/4 + 3/4 * [(1/2)^(A(1)+B(1)) + (1/2)^(A(2)+B(2)) + (1/2)^(A(3)+B(3)) + ...]

But, what we have in [.......] is exactly S. Therefore :

S = 1/4 + 3/4 * S

Finally, S - 3/4 * S = 1/4 ====>S = 1.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Puzzle Answer	K Sengupta	2022-05-26 23:00:31
re: Great problem -- and comments!	pcbouhid	2005-08-30 14:38:40
Great problem -- and comments!	Rebecca Jaffe	2005-08-30 03:16:20
Chunking A(n) -- Simplified	Gamer	2005-08-21 04:11:25
Chunking A(n) -- Explained	Gamer	2005-08-21 04:11:13
re: Suspicions confirmed	Josh70679	2005-08-20 21:19:56
Suspicions confirmed	Paul	2005-08-20 20:32:01
Looks suspiciously close to ...	Charlie	2005-08-20 18:54:22

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info