Determining which number lies in sequence $1234567891011\ldots$ on the $10^{100005}$'th position

Question

We have the infinite sequence made from concatenation of consecutive natural numbers: $123456789101112131415\ldots$ There is also a function $f$, where $f(n)=k$ if the digit on the $10^n$'th position is from natural number with $k$ digits (so for example $f(1)=2$ because on the $10$'th position in the sequence there is $1$ from $10$, which is a 2-digit number.

The problem asks us to find $f(100005)$.

This is a problem from an exam from my discrete math class, yet I don't know which concept should I use. I only covered sums, binomial coefficients, generating functions, Stirling numbers and Inclusion-exclusion principle. I don't see however how any of these concepts are connected to this problem. Any hints?

I mis-edited it, assuming he was asking digit, but then saw the question in more detail. @barakmanos — Thomas Andrews, Mar 28 '15 at 14:35
@ThomasAndrews: Then what does the word "position" mean in the context of this question? — barak manos, Mar 28 '15 at 14:37
$f(n)=k$ if and only if on the $10^n$'th position in the sequence $123456789101112...$ there is a digit from $k$-digit natural number. — qiubit, Mar 28 '15 at 14:37
possible duplicate of Find the $n^{\rm th}$ digit in the sequence $123456789101112\dots$ — Elaqqad, Mar 28 '15 at 14:38
this pdf is useful https://myows.com/protects/copyright/67407_mathexploration-pdf — Elaqqad, Mar 28 '15 at 14:39
@Elaqqad: This is similar, but the result asked for is the decade we are in rather than the digit itself. The same technique works. — Ross Millikan, Mar 28 '15 at 14:39
@user46944: I believe you take the digit in the $10^n$ th position and ask how many digits are in the number it came from. So for $f(4)$ you ask how many digits are in the the numbers that make of the block containing the $10^4$th digit. In this case the three digit numbers end at digit $2889$ and the four digit numbers end at digit $38889$, so the $10^4$ digit comes from a four digit number and $f(4)=4$ — Ross Millikan, Mar 28 '15 at 14:46
@Elaqqad While that is related, I don't think it is a dupplicate. — Thomas Andrews, Mar 28 '15 at 14:54

score 5 · Answer 1 · answered Mar 28 '15 at 14:38

There are $9$ one digit numbers, which fill the first $9$ positions. There are $90$ two digit numbers, which fill the next $180$ positions. There are $900$ three digit numbers, which fill the next $2700$ positions. The position at the end of the $k$ digit numbers is $\sum_{i=1}^k9i10^i$ You need to sum this series and find the smallest $k$ such that the sum is greater than $10^{100005}$

Thomas Andrews · Answer 2 · 2015-03-28T15:08:53.677

4

So, define $g(n)$ to be the number of digits of the number at the $n$th digit of this number.

You are looking for $f(n)=g(10^n)$.

$g(n)=k$ if and only if:

$$1+\sum_{i=1}^{k-1} i(10^{i}-10^{i-1})\leq n < 1+\sum_{i=1}^{k} i(10^i-10^{i-1})$$

So you need a closed form for $$m(k)=1+\sum_{i=1}^{k} i(10^i-10^{i-1})=1+9\sum_{i=1}^k i10^{i-1}$$

It can be shown that:

$$\sum_{i=1}^{k-1} iz^{i-1} = \frac{(k-1)z^k - kz^{k-1}+1}{(z-1)^2}$$

With $z=10$ this gives $$m(k)=\frac{1}{9}\left((k-1)10^k-k10^{k-1}+10\right)$$

Then you are trying to find the smallest $k$ so that $m(k)>10^{100005}$.

Definitely $k\approx 100000$. You'd have to try some values.

edited Mar 28 '15 at 15:08

answered Mar 28 '15 at 14:53

Thomas Andrews

177,126

$(+1)$ But there are some typos: With your definition of $m(k)$, we have $g(n)=k$ iff $m(\color{blue}{k})\le n\lt m(\color{blue}{k+1})$, so we're trying to find the smallest $k$ such that $m(k\color{blue}{\mathbb{+1}})>n=10^{100005}$, which turns out to be $k=100001$ by computerized search. ($m(k)$ is the index of the first digit of the smallest $k$-digit natural number being concatenated, i.e., the index of the $1$ in $10^{k-1}$.) – r.e.s. Nov 01 '17 at 23:53

Determining which number lies in sequence $1234567891011\ldots$ on the $10^{100005}$'th position

2 Answers2