# Find subsequence A in sequence B A007908 - OEIS

I have sequence A as A007908 - OEIS and pattern B which is a sub-sequence of that sequence A. I need to find index of first occurrence of the given pattern. For example pattern ..1010...

I've looked at this. Could anyone explain how to solve the problem?

Finding a formula for a pattern

• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – Michael E2 Oct 2 '15 at 19:06
• Your question could be a question about the software system Mathematica, but it seems from the link like it might belong on math.SE instead. Could you say more? (See mathematica.stackexchange.com/help/on-topic) – Michael E2 Oct 2 '15 at 19:07
• Can you construct a simple example that you can include in the question instead of making folks go to some external site? – george2079 Oct 2 '15 at 19:08
• possible duplicate: mathematica.stackexchange.com/questions/941/… ( Unless the specific input sequence makes a difference ) – george2079 Oct 2 '15 at 19:17
• Flatten[ IntegerDigits[ Range@# ] & /@ Range[ n ] ] – george2079 Oct 2 '15 at 19:21

## 1 Answer

Using the findSubsequence function from the linked answer: https://mathematica.stackexchange.com/a/942/2079

 findSubsequence[list_, {ss__}] :=
ReplaceList[list, {pre___, ss, ___} :> Length[{pre}] + 1]


suppose we have b:

 b = {8, 4, 9, 1, 2}


In principle you search the full sequence:

 findSubsequence[Flatten[IntegerDigits[Range@#] & /@ Range[FromDigits[b]] ,b]
(*huge, dont do it*)


Find the first subsequence long enough to contain b:

 i = 1; While[ Length@Flatten[IntegerDigits[Range@i] ] < Length@b,
i++]; i


5

check if b occurs early..

 findSubsequence[Flatten[IntegerDigits[Range@#] & /@ Range[i]] , b]


{}

beyond here we need only look in adjacent pairs:

 While[
findSubsequence[
Flatten[Join[IntegerDigits[Range[i]],
IntegerDigits[Range[i + 1]]]], b] == {}, ++i]; i


49

now a manageable* full search up to that i:

 findSubsequence[Flatten[IntegerDigits[Range@#] & /@ Range[i + 1]] , b]


{2043}

*manageable because I picked a sequence I knew occurred pretty early..You can readily eliminate that last search by keeping a cumulative tally of all the sub-sequence lengths.

Edit: a little cleaner version tracking the lengths...

 b = {8, 4, 9, 1, 2}
i = 1; While[ Length@Flatten[IntegerDigits[Range@i] ] < Length@b,
i++]; i
early = Flatten[IntegerDigits[Range@#] & /@ Range[i]];
findSubsequence[early , b]
res = NestWhile[  {
z = Flatten@IntegerDigits[Range[#[] + 1]],
#[] + 1, #[] + Length@z } & ,
{Flatten@IntegerDigits[Range[i]], i , Length@early} ,
findSubsequence[ Flatten[Join[#1[], #2[]]], b] == {} &,
2 ];
lastseq = Flatten@IntegerDigits[Range[res[] - 1]]~Join~
Flatten@IntegerDigits[Range[res[]]];
res[] - Length@lastseq + First@findSubsequence[ lastseq, b]


2043

• Pending clarification from the OP, I don't think this answers the question, unless they're abusing terminology in subsequence... – ciao Oct 3 '15 at 7:36