# Counting zero-digits between 1 and 1 million

I just remembered a problem I read years ago but never found an answer:

Find how many 0-digits exist in natural numbers between 1 and 1 million.

I am a programmer, so a quick brute-force would easily give me the answer, but I am more interested in a pen-and-paper solution.

-
See this. –  Guess who it is. Jul 14 '12 at 15:24
You could optimize your program until all that's left is "return x;". Some of the mathematical calculations will be mostly equivalent to doing that. –  Hurkyl Oct 2 '13 at 17:46

Just to show there is more than one way to do it:

How many zero digits are there in all six-digit numbers? The first digit is never zero, but if we pool all of the non-first digits together, no value occurs more often than the others, so exactly one-tenth of them will be zeroes. There are $9\cdot 5\cdot 10^5$ such digits all of all, and a tenth of them is $9\cdot 5 \cdot 10^4$.

Repeating that reasoning for each possible length, the number of zero digits we find between $1$ and $999999$ inclusive is $$\sum_{n=2}^6 9(n-1)10^{n-2} = 9\cdot 54321 = 488889$$ To that we may (depending on how we interpret "between" in the problem statement) need to add the 6 zeroes from 1,000,000 itself, giving a total of 488,895.

-

This solution might appeal to a programmer's mind. Let's say we zero-pad (to $6$ digits) the million numbers from $0$ to $999999$. Then each of the $6$ positions uses each digit equally, for a total of $6000000/10 = 600000$ zeros.

Now note that compared to the actual question, we included $000000$, and excluded $1000000$, which balances out nicely. We just need to undo the zero-padding: there are $9$ positive one-digit numbers which were padded by 5, $90$ two-digit numbers padded by $4$, etc. What remains is

$$600000 - 5\cdot9 - 4\cdot90 - 3\cdot900 - 2\cdot9000 - 1\cdot90000 = 488895.$$

-

Consider the number of ways we may have a $0$ in the ones place. We may have $10, 20, 30\cdots 999990$. These are just the naturals $1, 2\cdots99999$ with a zero on the end.

However, we may also put a zero in the tens place. This may take the form of $100, 101\cdots999909$. These are the naturals $10,11\cdots99999$ with a zero injected before the ones place.

Similarly, we may count the zeros in the other places by considering the naturals into which they can be injected. Each position further left for the zero will require multiplying the starting number by ten to give a nonzero digit to the left.

The zeros required to write one to a million are $99999 + (99999 - 9) + (99999 - 99) + (99999 - 999) + (99999 - 9999) = 488889$.

EDIT: If you mean one to one million including the million, you have to add six to get $488895$. I guess I was thinking like a programmer too with the exclusive upper bound!

-