1
$\begingroup$

A dedicated person is going to write down all numbers in the range $[0, 10^9)$. It takes 1 second to write down 1 digit.

The numbers in the range $[0, 100)$ takes 190 seconds to write: $10$ seconds for $[0, 9]$ + $2*90$ seconds for $[10, 99]$.

How long would it take to write down all numbers in the range $[0, 10^9)$?

$\endgroup$
11
  • $\begingroup$ Hint : There are $9\cdot 10^{n-1}$ $n$-digit-numbers for $n\ge 2$ $\endgroup$ – Peter Aug 2 '18 at 10:10
  • 1
    $\begingroup$ How many numbers are there with each number of digits? Write down those counts. Multiply each by the number of digits. Add them all. (Even with pencil and paper this is probably just as fast as getting details of some more clever trick for summing the series right). $\endgroup$ – hmakholm left over Monica Aug 2 '18 at 10:10
  • 2
    $\begingroup$ Also, your dedicated person writes curiously slowly :-) $\endgroup$ – hmakholm left over Monica Aug 2 '18 at 10:12
  • 1
    $\begingroup$ @HenningMakholm One digit per second slow ? $\endgroup$ – Peter Aug 2 '18 at 10:13
  • 1
    $\begingroup$ @Servaes: Not quite that fast -- I just timed myself for 6 rows of 0123456789 and got 30 seconds. But then again I don't have the decades and decades of practice our hypothetical person will get. $\endgroup$ – hmakholm left over Monica Aug 2 '18 at 10:24
3
$\begingroup$

As others have already pointed out, it is easy to count the number of digits of all numbers between $10^{m-1}$ (included) and $10^m$ (excluded) - the $m$-digits-numbers: $$ \underbrace{\text{digits per number}}_{m}\cdot\underbrace{\text{how many numbers}}_{10^m - 10^{m-1}} $$ $$ = 9\cdot 10^{m-1} \cdot m $$ Note that for two different values of $m$ there is no number that contributes more than once.

Be $\mathrm{d}(n)$ the number of digits of all numbers between $0$ (included) and $10^n$ (excluded), it is a matter of considering the target quantity until $10^{n-1}$ (represented by $\mathrm{d}(n-1)$) and the number of $n$-digits-numbers: $$ \mathrm{d}(n) = \begin{cases} 1 & n = 0 \\ \mathrm{d}(n-1) + 9\cdot 10^{n-1} \cdot n & n > 0 \end{cases} $$ Giving: $$ \begin{align} \mathrm{d}(n) &= 1 + \sum_{k=1}^n 9\cdot 10^{n-1} \cdot n \end{align} $$ We’ll use Wolfram Alpha to obtain the closed formula of that series: $$ \begin{align} \sum_{k=1}^n 9\cdot 10^{n-1} \cdot n&=10^n\cdot n-\frac{10^n}{9}+\frac{1}{9}\\ &=10^n\cdot n + \frac{1-10^n}{9} \end{align} $$ Finally: $$ \mathrm{d}(n) = 1+10^n\cdot n + \frac{1-10^n}{9} $$ Let’s verify that we have indeed found the right formula: $$ \begin{array}{c|c} n & \mathrm{d}(n) \\ \hline 1 & 10\\ 2 & 190\\ \vdots & \vdots \\ 9 & 8888888890 \end{array} $$

Epilogue - Be $\mathrm{t}(n)$ how many seconds it would take to write down all numbers one next to the other between $0$ and $10^n$ given a speed of $v$ digits per second then: $$\mathrm{t}(n) = \frac{\mathrm{d}(n)}{v}$$

The number of years $\mathrm{y}(n)$ needed at least (given a $365$ days long year) is: \[\mathrm{y}(n) = \left\lfloor\frac{\mathrm{t}(n)}{3600\cdot24\cdot365}\right\rfloor\]

$\endgroup$
2
  • 1
    $\begingroup$ Your simplification of the closed form of the sum seems wrong; it isn't even an integer for $n=1,2,3,\ldots,8$. And in the epilogue, shouldn't that be $\mathrm{t}(n) = \frac{\mathrm{d}(n)}{v}$? $\endgroup$ – Servaes Aug 3 '18 at 9:10
  • $\begingroup$ @Servaes Thank you very much, I corrected them. $\endgroup$ – Giulio Scattolin Aug 3 '18 at 9:17
3
$\begingroup$

As another way to calculate it, first imagine all $10^9$ numbers written out padded with zeroes on the left to make each of them 9 digits long. That makes $9\,000\,000\,000$ digits.

Then erase $10^8$ leading zeroes in the first column.

Then erase $10^7$ leading zeroes in the second column.

Then erase $10^6$ leading zeroes in the third column.

And so forth. At the end you don't erase the single remaining zero in the number $0$, so you end up with $$ 9\,000\,000\,000 - 111\,111\,110 $$ digits.

$\endgroup$
1
$\begingroup$

282 years of writing digits non-stop 24/7

or

$8888888890$ seconds


The answer was found using this Python expression:

1 + sum([(10**(x+1) - 10**x) * (x+1) for x in range(9)])

By replacing range(9) with other ranges, it's easy to check that the lower values are correct:

  • With range(0): $[0,10^0)$ has 1 digit.
  • With range(1): $[0,10^1)$ has 10 digits.
  • With range(2): $[0,10^2)$ has 190 digits.
  • With range(3): $[0,10^3)$ has 2890 digits.

(This is not a proper proof, though).

$\endgroup$
1
  • 1
    $\begingroup$ Good enough to answer the question, I think. $\endgroup$ – David R. Aug 2 '18 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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