0
$\begingroup$

A binary string is a word containing only $0$s and $1$s. In a binary string, a 1-run is a non-extendable substring containing only $1$s. Given a positive integer n, let B(n) be the number of $1$-runs in the binary representation of n. For example, B(107) = 3 since 107 in binary is 1101011 which has exactly three 1-runs. What is the following expression equal to?

$B(1) + B(2) + B(3) + · · · + B(255)$

I have solved the problem, I would like to see how others approach the problem or if there is more elegant solution to it. For spoiler, I will add my approach in the comment.

$\endgroup$
3
  • $\begingroup$ My approach was to check how many 1-runs are there in an n digit number(binary) and try to write it in terms of 1-runs using smaller numbers. An n-digit number starts with a 1. If it follows by a zero, it will increase 1 run. So, the total number of 1 run in a n digit number would be the sum of 1-run in less than n digit + total number of n-digit numbers /2. If my calculation is right, it turns out to be 1+2+5+12+28+64+144=256 $\endgroup$
    – Economics User
    Commented Jan 3, 2022 at 6:33
  • $\begingroup$ Maybe this can be inspiring. $\endgroup$
    – drhab
    Commented Jan 3, 2022 at 8:36
  • $\begingroup$ @drhab Thank you, I am a member of it. $\endgroup$
    – Economics User
    Commented Jan 4, 2022 at 6:55

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .