Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}}$

share|improve this question
    
Note that there are $9\cdot 10^{k-1}$ $k$-digit numbers between $10^{k-1}$ and $10^k-1$. –  J. M. 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... :) –  J. M. Nov 2 '10 at 3:13
add comment

3 Answers

up vote 2 down vote accepted

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}.$$

share|improve this answer
    
Thank you, Derek! Nice resolution! –  Paulo Argolo Nov 2 '10 at 14:13
add comment

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...

share|improve this answer
    
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. –  J. M. 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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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