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

2 Answers 2

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, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .