5
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ I think that will get you something very like the formula given at oeis.org/A033307 $\endgroup$ Feb 21 '13 at 0:56
2
$\begingroup$

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$

$\endgroup$

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.