Counting 0's in Binary

Lemma: In base $b$ , the number of 0's that are needed to write the numbers with exactly $k \geq 2$ digits, is $(k-1) \times (b-1) \times b^{k-2}$ .

Proof: Consider the number of times when the ith position from the right is a 0.
For the $k$ th position from the right, this number cannot be a 0.
Otherwise, for each of the other $i \neq k$ positions, there are $(b-1)$ possibilities for the first digit, 1 possibility for the $i$ th digit, and $b$ possibilities for each of the other digits. Hence, by rule of product, there are $(b-1) \times b^{k-2}$ times when the $i$ th digits is 0.
Since there are $k-1$ possibilities for $i$ , hence the number with exactly $k$ digits will use $(k-1) \times (b-1 ) \times b^{k-2}$ zeroes.

---

We now apply this to the case of $b = 2$ .
For the positive integers that have 1 digit, none of them are 0.
For the positive integers that range from having $2, 3, 4, 5, 6, 7, 8$ digits, the number of zeros that we use is

$1 \times 1 \times 2^0 + 2 \times 1 \times 2^1 + 3 \times 1 \times 2^2 + 4 \times 1 \times 2^3 + 5 \times 1 \times 2^4 + 6 \times 1 \times 2^5 + 7 \times 1 \times 2^6 = 769$

Now, when we account for $256 = 100000000_2$ which has 8 zeroes, and $0 = 0_2$ which has 1 zero, the number of zeroes that we use is $769 + 8 + 1 = 778$ .

If the numbers 0 through 255 are written with eight bits, all possible combinations of ones and zeros are present. By symmetry, there are equal numbers of zeroes and ones. Thus we have $\frac{256\times 8}{2} = 1024$ zeroes. However, we must remove leading zeroes.

There are 128 numbers where bit 7 is zero. Of these, 64 have bit 6 also equal to zero. Of those, 32 have bit 5 also equal to zero. And so on; this means that we remove $128 + 64 + \cdots + 1 = 2^7 + 2^6 + \cdots + 2^0 = 2^8-1 = 255$ leading zeroes, so that we now have $1024 - 255 = 769$ zeroes in total.

Two things need adjusting. First, we removed all eight zeroes of $0 = 00000000_2$ ; thus we add one back in. Second, we must add the eight zeroes of $256 = 100000000_2$ . This results in the answer $769 + 1 + 8 = \boxed{778}.$

At first notice that, in binary number system 256 is equal to 100000000. And it is the first nine-digit binary number.
Then notice that one-digit binary number has no zero.
Two-digit binary numbers have 1 zeros.
Three-digit binary number has 4 zeros.
Four-digit and five-digit binary numbers have 12 and 32 zeros respectively.

Here we can find a series that--
0+1+4+12+32+... ... ...
we can except 0. So the series becomes --
1+4+12+32+... ... ...
If we find the number of zeros in one to eight digit binary numbers, our work will almost done.
In the series we can see that nth term of the series is n*(2^(n-1)). So the 5th, 6th and 7th term will be 80, 192 and 448 respectively. So the sum of the first 7th term of the series is (1+4+12+32+80+192+448) or, 769.
So, the number of zeros in one to eight digit binary numbers is 769. That means if we write 1 to 255 in binary number system, we will need to write 769 zeros.
But our work is not completely done yet.
In 256, there is 8 zeros and in binary number system 0 is also 0. So we will need to write zero once more.
Total = 769+8+1
. =778
That's our answer.

Let us consider n-digit binary numbers. The first digit from the left can not be 0.
So there are only (n-1) spaces for 0s.
Number of binary number with n digits with left most 1 is $2^{n-1}$ .
So for an n-digit number, there are $(n-1)*2^{n-1}$ locations to be filled.
But 0 and 1 has equal claim. So 0s possible are $\frac 1 2 *(n-1)*2^{n-1}= (n-1)*2^{n-2}$ . Now the number we are interested is $0_2 \ to\ 100000000_2$ .
The first 0 and the last 8 0s does not fit in our formula. They are 1+8=9 0s.
Total zeros = $\displaystyle 9+ \sum_{n=1}^8 (n-1)*2^{n-2}=9+769=\huge\ \ \color{#D61F06}{778}$ .

1. We have one 0 for the beginning zero,
2. 8 zeros for 256 written in binary form,
3. This step needs explanation.

Consider all eight digit binary numbers. U need at most 7 and at least 1 zero. To find the numbers having 7 zeros is equivalent finding how many ways u can put no one given 7 empty boxes, thus ${7\choose0}$ So total number of zeros used in writing these numbers is simply $7× {7\choose0}$

To find the numbers having 6 zeros is equivalent finding how many ways u can put 1 one given 7 empty boxes, thus ${7\choose1}$ . Thus the number of zeros here $6× {7\choose1}$

We can sum up all these numbers to get the number of zeros to write an eight digit binary number. To generalise, it can be written

$\sum_{i=1}^7 i× {7\choose(7-i)}=448$

U can repeat this process to for 7,6, 5, …..,2 digit numbers. Finally u will get

$448+192+80+32+12+4+1=769$

1. Add up the zeros from 1st two steps and u will find the ans 778.

My process is a bit tedious. I think double summation would reduce a lot of works. But i don't know it clearly. If anyone know then please explain.