5
$\begingroup$

How many times does the digit $0$ occur in the list of numbers from $1$ to $10^{100}$, inclusive?

$\endgroup$
3
  • 5
    $\begingroup$ And list all the numbers in which it occurs... ;-) $\endgroup$
    – Stiv
    Dec 6, 2023 at 13:37
  • $\begingroup$ hehe good luck with that :) $\endgroup$ Dec 6, 2023 at 14:31
  • 1
    $\begingroup$ Are we considering leading zeros as well? $\endgroup$ Dec 6, 2023 at 15:11

2 Answers 2

5
$\begingroup$

Observe that the numbers of occurrences of zeroes from $0$ to $10^n-1$ follow this sequence 0, 1, 10, 190, 2890, 38890, ... (oeis)

those numbers can be obtained for any $n > 2$ as
$10^{n-1} + \sum_{i=2}^{n-1} (10^{n-1}-10^{n-i})$
Where each summation member is the number of occurrences of the zeroes in the $i$-th position starting from right and $10^{n-1}$ is the count of zeroes in the first position.

ie. for $n=4$ we count all zeroes between 0 and 9999
$10^3+(10^3-10^2) + (10^3-10) = 2890$

plugging in $n=100$ we obtain:
$ 10^{99} + \sum_{i=2}^{99} (10^{99}-10^{100-i})$

Now we have to move the range from $[0,10^n-1]$ to $[1,10^n]$.

To achieve this, we have to subtract the first zero count and add 100 zeroes from the googol itself to get the final answer:
$ 10^{99} + \sum_{i=2}^{99} (10^{99}-10^{100-i})$ - 1 + 100 = 98888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888989

Bonus

To easily get the n-th entry (ignoring the first "$0$" term) of the OEIS serie above, for $n >= 3$ you can use this simple trick:

- write $n - 2$
- append $8$, $n-3$ times
- append $90$

for $n=100$
- $98$
- $8888.....8888$ (97 eights)
- $90$

$\endgroup$
3
  • $\begingroup$ Nice! Can you write the answer in closed form, just for clarity? Thanks. $\endgroup$ Dec 6, 2023 at 14:51
  • $\begingroup$ It is easier to count all zeros (proper and leading) first: N x 10^(N-1) and then subtract leading zeros: 1+10+100+1000+... (N terms). (Add back 1 if you want to count 0 as a legit 0 even though it is leading.) $\endgroup$ Dec 6, 2023 at 19:36
  • 1
    $\begingroup$ Great work and thanks for finding the sequence. There is actually a closed form formula in the OEIS, which you can use here. $\endgroup$ Dec 7, 2023 at 11:26
1
$\begingroup$

Consider the last $100$ digits of each of these numbers, padded with leading zeroes as necessary.

Now consider reversing each of these strings. Since we're counting all $10^{100}$ $100$-digit strings, this is a bijection, and it has the effect of turning leading zeroes into trailing zeroes, with the exception of the all-zeroes string we got from $10^{100}$. Therefore, the trailing zeroes that we wish to count are half of all the zeroes, plus the other $50$ from the all-zeroes string.
Each position in the string has a $0$ in exactly one-tenth of the strings each, and there are $100$ positions, so the total zeroes are $\frac{\frac{10^{100}}{10}100}{2}+50 = 5×10^{100}+50$.

$\endgroup$
3
  • $\begingroup$ I got a different answer which matches the other answer posted $\endgroup$ Dec 6, 2023 at 14:21
  • 3
    $\begingroup$ It's a good try, but you forgot about palindromes. $\endgroup$ Dec 6, 2023 at 14:53
  • 5
    $\begingroup$ What about zeros that are neither trailing nor leading? $\endgroup$ Dec 6, 2023 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.