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.

Consider the following sequence: $$1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 0, 2, 1, 2, 2, 2, 3, \ldots$$ which is formed by extracting the digits of the natural numbers. Is there any formula for the general term of this sequence?

All I can think of is an algorithm to obtain its terms:

"Set $n = 1$. While $n$ is not too big {extract digits from $n$ and insert them into the sequence, then set $n = n + 1$}"

share|improve this question
    
Is n mod 10 good enough? –  Dylan Yott Feb 21 '13 at 0:44
    
@Dylan, $n\mod{10}$ just gives $0$ through $9$, repeating, which isn't the right sequence. –  Gerry Myerson Feb 21 '13 at 0:50
2  
A formula is given at oeis.org/A033307 but it involves the Lambert $W$-function. –  Gerry Myerson Feb 21 '13 at 0:54
    
@GerryMyerson you're absolutely right, I read this much too quickly. –  Dylan Yott Feb 21 '13 at 1:55

2 Answers 2

up vote 3 down vote accepted

Given a number $n$, the total number of digits to represent $1$ to $n$ can be obtained as follows.

Let $k = \left \lfloor \log_{10}(n) \right \rfloor$. Then the number of digits from $1$ to $10^k-1$ is given by $$\sum_{l=1}^k l \cdot 9 \cdot 10^{l-1} = k \cdot 10^k - \dfrac{10^k-1}9$$ Hence, the number of digits needed to list $1$ to $n$ is $$f(n) = \underbrace{k \cdot 10^k - \dfrac{10^k-1}9}_{\text{Number of digits from $1$ to $10^k-1$}} + \overbrace{(k+1)\left(n+1-10^k\right)}^{\text{Number of digits from $10^k$ to $n$}} = (n+1)(k+1) - \dfrac{10^{k+1}-1}9$$ where $k = \left \lfloor \log_{10}(n) \right \rfloor$. The function you are after is the inverse of $f(n)$.

share|improve this answer
    
I think that will get you something very like the formula given at oeis.org/A033307 –  Gerry Myerson Feb 21 '13 at 0:56

You can calculate how many digits are represented by each decade. The one digit numbers supply the first $9$ terms, the two digit numbers supply $2\cdot 90=180$, the three digit numbers the next $3\cdot 900=2700$ and so on. If you want to find the digit at position $n$, first find the decade you are in. The $d$ digit numbers end at $\sum_{i=1}^d 9\cdot i \cdot 10^{i-1}=9\frac{d10^{d+1}-(d+1)x^d+1}{81}=\frac{d10^{d+1}-(d+1)x^d+1}{9}$. Then figure out where you are in the decade. For example, if you want the $5000$th term, the one, two, and three digit numbers fill $2889$, so we want the $2111$st term of the four digit numbers. This is part of the $\lceil \frac {2111}4 \rceil = 528$th number, which is $1527$. Then it is the $2111-1 \pmod 4 +1=3$rd digit of this, so $2$

share|improve this answer

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.