# Number of digits from 1 to n

Let $n$ be a natural number $k$ digits. Show that the quantity $Q$ of digits required to write the natural numbers from $1$ to $n$ is:

$Q = k(n+1) - \underbrace{111\ldots11}_{k\textrm{ digits}}$

-
Note that there are $9\cdot 10^{k-1}$ $k$-digit numbers between $10^{k-1}$ and $10^k-1$. –  Guess who it is. Nov 1 '10 at 23:24
Close, but not quite. If you plug n=9, k=1 in (I think you are assuming n=10^k-1) it doesn't come out. You need k digits 1, not n. The usual way to write it would be to say the number of digits to write all the numbers from 1 through 10^k-1 is k(10^k)-(10^k-1)/9. This way you don't need n. Good on you for working it out. –  Ross Millikan Nov 2 '10 at 1:32
I think the choice of whether to express the function Paulo wants in terms of $k$ or $n$ is cosmetic... :) –  Guess who it is. Nov 2 '10 at 3:13

As this question is now 14 hours old, I will give an answer.

First sum the total number of digits of all the natural numbers $\le k-1.$ Call this sum $S.$

There are $9 \times 10^{i-1}$ natural numbers of length $i,$ so the total number of digits of natural numbers of length $i$ is $9i \times 10^{i-1}.$ Hence

$$S=9(1+2.10 + 3.10^2 + \cdots + (k-1)10^{k-2}) = (k-1)10^{k-1} - \frac{10^{k-1}-1}{9}.$$

Now the first natural number with $k$ digits is $10^{k-1}$ and so there are $n- 10^{k-1}+1$ natural numbers from $10^{k-1}$ to $n$ inclusive. Each of these numbers has $k$ digits and so the number of digits required to write the natural numbers from $1$ to $n$ is

$$k( n- 10^{k-1}+1) + S = k( n- 10^{k-1}+1) + (k-1)10^{k-1} - \frac{10^{k-1}-1}{9}$$

$$= k(n+1) - \frac{10^k-1}{9}.$$

-
Thank you, Derek! Nice resolution! –  Paulo Argolo Nov 2 '10 at 14:13

Start with the one digit numbers. How many digits are needed for them. Do you include zero? How many digits to go from 10 through 99? And so on...

-
What I want is to get a formula for the number of digits, depending on n and k. –  Paulo Argolo Nov 1 '10 at 23:30
Well, he did say 1 to n in the original question... :) @Paulo: your function will be complicated and will only depend on n, since as you know k can be obtained from n through appropriate formulae. –  Guess who it is. Nov 1 '10 at 23:37
Yes, and with what J.M. commented and what is above, you should be able to make one. It is pretty easy to come up with one if n is 10^p-1 so you count all the p digit numbers. The expression is a little messier if you stop in the middle of a decade. –  Ross Millikan Nov 1 '10 at 23:38
I gave the issue new writing. –  Paulo Argolo Nov 2 '10 at 0:24

HINT $\$ Chopping off the unit digit is a 10-to-1 map from k+1 digit onto k-digit naturals. Therefore, since there are 9 naturals with 1-digit, there are 90 with 2-digits, and 900 with 3-digits, etc.

-
I made the correction: 111 ... 11 contains k digits equal to 1. Thanks, Ross Millikan! –  Paulo Argolo Nov 2 '10 at 10:06
@Paulo: Was your comment intended for Ross's answer? –  Bill Dubuque Nov 2 '10 at 15:54
Yes, it was, Bill. –  Paulo Argolo Nov 2 '10 at 16:34
@Paulo: Ok, so let's delete our comments here then so as not to confuse anyone. –  Bill Dubuque Nov 2 '10 at 17:31