A math puzzle from a friend who is on a math team:
The irrational number: $0.12345678910111213141516171819\dots$ has the string $314$ first occurring starting at the $17$th decimal place. When does the first occurrence of $2012$ start?
The answer to this puzzle is $251$.
I am interested in solving a general form for any occurring number. There are many cases so this might be a piecewise function.
On
You can easily program this out, with the following algorithm:
Step 1: Split a given integer of n digits in 2 digit-sequences by viewing the first $ 0 \leq i \leq n-1$ as the first sequence(can be an empty sequence) and the next $n-i$ digits to be the second sequence. In this way we have n different splits.
Step 2: Verify which splits are 'good' splits. Good splits are splits such that, there is a integer ending with sequence 1 and a integer starting with sequence 2. In the 2012 case, we have 4 possible (different) splits:
In this case all but the second are good splits, because there is not integer which starts with the digits 012.
Step 3: After filtering, look at the ones who are good splits and calculate when they appear. And the answer to the question is the minimum of all these values. Calculating the appearance is done like this:
Given a split (ab)(cdefg), calculate the minimal integer $d$ such that d starts with (cdefg) and ends with (ab+1). If $a \neq g$ then it is the integer $cdefgab+1$ for example. Then the digit where this integer occurs is $9*1+90*2+900*3+900*4+9000*5+90000*6+(cdefgab+1-10^6)*7+1-2$ in our case. The first 6 terms are there because our integer is bigger than 10*6, so all those integers come before him. Then there are $cdefgab+1-10^6$ integers before him with 7 digits. So this integer would start at the next place (+1 part) but since we want $abcdefg$, we can substract 2 places because this new integer starts 2 places earlier.
Given an $n$-digit pattern, we clearly have an appearence where the corresponding number itself is inserted in the string. Appearences at earlier numbers are possible if we split the pattern into $d$ and $n-d$ digits (the latter not starting with $0$): we can find our pattern where the number formed by the right subpattern followed by the left subpattern occurs (decrease the right subpattern by one first if the left subpattern is all nines). Thus 2012 can also be found in $12\underline{ 20\, 12}21$ and in $2\underline{201\, 2}202$. It remains to check for $1\le m\le k<n$ whether interpreting the first $m$ digits as tail of a $k$ digit number leads to a match for all full and partial blocks thus determined. Here, with $k=1$, there is no match beacuse $2$ is followed by $0$ instead of $3$. With $k=2$, there is no match if $m=1$ because the next part $01$ has a leading $0$ and if $m=2$ no match because $20$ is followed by $12$ instead of $21$. With $k=3$ we have the options $\underline{201\,2}02$ and $x\underline{20\,12}y$ which leads to $1\underline{20\,12}1$ and hence the earliest appearence. After this $O(n^2)$ trial and error phase it is comparatively easy do compute the number of digits preceding the found appearence.