6

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.

user14069
  • 1,305
  • 2
    Hmm...the answer $251$ makes sense because $2012$ occurs in the concatenation of $120$ and $121$, so we obtain: $$ 9(1)+90(2)+(120-100+1)(3)-1=251 $$ – Adriano Jul 18 '13 at 17:42
  • This might be useful: http://oeis.org/A116700

    and this: http://oeis.org/A220376

     – picakhu Jul 18 '13 at 17:43
  • If the digits of the target string are in increasing order, then it seems that its first occurrence will be when that integer occurs (it won't span concatenated integers)...hmm. – Adriano Jul 18 '13 at 17:48
  • As Adriano showed, once you know which consecutive numbers combine to produce the first occurrence (i.e., 120 and 121 produce the first occurrence of 2012), it is easy to calculate the number of digits already seen. The first part is the only tricky part. I guess you could consider all positions for the first "cut" (for example, look for "2 012," "20 12," "201 2," or "2012") and choose the best one... not sure if there's a slicker way that works for any number. – angryavian Jul 18 '13 at 17:49

2 Answers2

2

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.

Hagen von Eitzen
  • 374,180
0

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:

  • () , (2012)
  • (2), (012)
  • (20), (12)
  • (201), (2)

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.

bbnkttp
  • 1,909
  • This method may miss a good "multisplit" for longer patterns, e.g. $24,725,72$ – Hagen von Eitzen Jul 18 '13 at 17:58
  • True. But checking if a pattern admits a multisplit can be done quadraticly in the length of the pattern, by checking if one of the $\frac{n^2-1}{2}$ possible 'double' cuts has a integer as middle sequence and walking to the outside of the sequence yields the expected digits until one comes to the end on both sides. This will yield all possible multisplits, I think, also with more than 2 cuts. When there is such a possibility then this is the way to go for the minimum. – bbnkttp Jul 18 '13 at 18:11