6
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\begingroup$ 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! $\endgroup$
    – Michael E2
    Oct 2, 2015 at 19:06
  • $\begingroup$ 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) $\endgroup$
    – Michael E2
    Oct 2, 2015 at 19:07
  • $\begingroup$ Can you construct a simple example that you can include in the question instead of making folks go to some external site? $\endgroup$
    – george2079
    Oct 2, 2015 at 19:08
  • $\begingroup$ possible duplicate: mathematica.stackexchange.com/questions/941/… ( Unless the specific input sequence makes a difference ) $\endgroup$
    – george2079
    Oct 2, 2015 at 19:17
  • 1
    $\begingroup$ Flatten[ IntegerDigits[ Range@# ] & /@ Range[ n ] ] $\endgroup$
    – george2079
    Oct 2, 2015 at 19:21

1 Answer 1

Reset to default
5
$\begingroup$

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[#[[2]] + 1]],
     #[[2]] + 1, #[[3]] + Length@z } & , 
     {Flatten@IntegerDigits[Range[i]], i , Length@early} ,
      findSubsequence[ Flatten[Join[#1[[1]], #2[[1]]]], b] == {} &, 
           2 ];
 lastseq = Flatten@IntegerDigits[Range[res[[2]] - 1]]~Join~
                Flatten@IntegerDigits[Range[res[[2]]]];
 res[[3]] - Length@lastseq + First@findSubsequence[ lastseq, b]

2043

Improve this answer
$\endgroup$
1
  • $\begingroup$ Pending clarification from the OP, I don't think this answers the question, unless they're abusing terminology in subsequence... $\endgroup$
    – ciao
    Oct 3, 2015 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.