My strategy for counting zeroes in a given number was the same as in Joanne's solution, so I won't repeat that here. My full Python code is below. It first establishes upper and lower bounds within which the solution must lie, and then bisects to find the exact solution. It runs instantaneously on my computer.

def zeroes(n):
    '''calculates count of 0 digits appearing in all integers [0..n]'''
    count = 1
    s = str(n)
    factor = 1
    for split in range(1, len(s)):
        front = s[:-split]
        back = s[-split:]

        count += factor*(int(front) - 1)
        count += min(int(back)+1, factor)

        factor *= 10
    return count

# establish bounds
lower = 1
upper = 2
while zeroes(upper) < upper:
    lower = upper
    upper *= 2

print 'must be between %d and %d' % (lower, upper)

# bisect to find solution
while True:
    middle = (lower + upper) / 2

    zm = zeroes(middle)
    if zm < middle:
        lower = middle
    elif zm > middle:
        upper = middle
    else:
        assert zm == middle
        print 'SOLVED', middle
        break

This is an interesting question. I have tried to solve it with a computer program but my program got time overrun, indicating that my programming sucks. I then came up with an analytic way of solving it. The program proves that the following equation I have come up with is correct.

$N\quad =\quad 1+\sum _{ i=1 }^{ n-1 }{ { 10 }^{ i-1 } } \left\lfloor \frac { M }{ { 10 }^{ i } } \right\rfloor -\sum _{ i=1 }^{ n-1 }{ u\left( { d }_{ i }=0 \right) } { 10 }^{ i }\left( 1-\left\lceil \frac { M }{ { 10 }^{ i } } \right\rceil \right)$

where

• $M$ and $N$ mean the same in the question

• $n=$ the number of digits of $M$

• $i = 0, 1,2...,n-1$ , the $i^{th}$ position of a digit of $M$ , $0$ being the last

• $d_{i}=$ the value of the $i^{th}$ digit of $M$

• $\left\lfloor x \right\rfloor =$ the largest integer smaller than or equal to $x$

• $\left\lceil x \right\rceil =$ the decimal residual of $x$

• $u\left( x=0 \right) =\begin{cases} 1,\quad if\quad x=0 \\ 0,\quad if\quad x\neq 0\quad \end{cases}$

1. The first term $1$ is for the case when $M=0$ .
2. The second term is for the fact that for every $10$ of $M$ , there is 1 zero; every $100$ , 10 zeros; every $10^{i}$ , $10^{i-1}$ zeros.
3. Statement 2 is not true if $d_{i}=0$ , the third term is to less out the $10^{i}$ zeros and add back the zeros due to the remainder (number right of $d_{i} + 1$ ).

I manually iterated using the equation with a spreadsheet to obtain the answer $\boxed{100559404365}$ .

Let's look at a random number (40321) and see if we can come up with a formula to calculate N.

To count in an organized fashion, we'll count all the values less than or equal to N that have a zero in the ones digit, then add that to all the numbers with a zero in the tens digit, and etc.

We'll first look at the numbers with a zero in its ones digit. Excluding the case when M=0 (we'll add that in the end), we know that there are 4032 numbers with a zero in the ones digit because the first four digits of the number could be anything between 1 and 4032.

Moving on to the tens digit, we can do something similar. The first three digits could be in one of 403 ways, the tens digit must be 0, and it doesn't matter what the ones digit is. Therefore, there are 403 * 10 = 4030 numbers with a zero in the tens place.

The same could be said for the hundreds place. The first two digits could be in one of 40 ways, and it doesn't matter what the last two digits are. Therefore, there are 40 * 100 = 4000 numbers with a zero in the hundreds place.

Now the thousands place is a bit different. If the thousands place is a zero, there are two different cases we must account for. If the ten thousands place is 1, 2, or 3, the last three digits can be anything, so there are 3 * 1000 = 3000 numbers that have a zero in the thousands digit. If the ten thousands place is 4, only 322 numbers have a zero in the thousands place (40000 to 40321). Therefore, there is a total of 3000 + 322 = 3322 numbers with a zero in the thousands place.

We know that there can't be a zero in the ten thousands place, so there we are done. We sum these numbers up, including 0: 4032 + 4030 + 4000 + 3322 + 1 = 15385 zeros that appear.

I decided to program this in Mathematica because Mathematica likes numbers. It took a while to run, but the answer does work.

x = 100559404365;
Sum[
  If[
   Mod[Floor[x/10^(i - 1)], 10] == 0, 
   (Floor[(x - 10^i)/10^i])*10^(i - 1) + Mod[x, 10^(i - 1)] + 1,
   Floor[x/10^i]*10^(i - 1)
   ],
  {i, Total@DigitCount[x]}] + 1

Basically, what we have found is that for the $i$ th digit from the right, if the digit is not equal to zero, the number of zeros that will occur on that particular digit is equal to

Floor[x/10^i]*10^(i - 1)

For the digits that are 0, the number of zeros that will occur is equal to

(Floor[(x - 10^i)/10^i])*10^(i - 1) + Mod[x, 10^(i - 1)] + 1

We just iterate this over all the digits and sum all the zeros and tada~ We're done.