Re: Seaching in Pi a sequence. Looking for a faster method
- To: mathgroup at smc.vnet.net
- Subject: [mg119659] Re: Seaching in Pi a sequence. Looking for a faster method
- From: rafapa <rafapa at us.es>
- Date: Thu, 16 Jun 2011 04:02:01 -0400 (EDT)
- References: <ita4fv$m7m$1@smc.vnet.net>
On Jun 15, 1:19 pm, Dana DeLouis <dana.... at gmail.com> wrote: > Hi. Just something a little different. > Given piesimo[10^7, 9, 7], You are looking for a specific digit (9) repeated a number of times (7). > > Here's what we have so far. > > Our String: > pi=StringDrop[ToString[N[Pi,10^7]],2]; > > Function: > piesimoS[m_String]:=First/@StringPosition[pi,m] > > Check Timing: > > piesimoS["9999999"]//Timing > {0.2513,{1722776,3389380,4313727,5466169}} > > This idea finds all sequences of the digit 9 repeated 7 or more times. > > DigitSequence[pi,9,7]//Timing > {0.08725,{{7,1722776},{7,3389380},{7,4313727},{7,5466169}}} > > It appears to be about 3 times faster. > That code returned the length of the sequence, and the starting position. > > (* s - String, d - digit to check, start - Minimum length *) > > DigitSequence[s_,d_,start_]:=Module[ > {re,z,t}, > z=StringReplace["n{s,}",{"n"->ToString[d],"s"->ToString[start]}]; > re=RegularExpression[z]; > t=StringPosition[s,re,Overlaps->False]; > t=t/.{x_Integer,y_Integer}:>{y-x+1,x}; > SortBy[SortBy[t,Last],First] > ] > > If you only wanted a specific length, then change rule to "n{s,s}" > > If you didn't know how many consecutive 9's there are in a string, then this finds 6 or more: > > DigitSequence[pi,9,6]//Timing > {0.08989, > {{6,762},{6,193034},{6,1985813},{6,2878443},{6,3062881}, > {6,3529731},{6,6951812},{6,7298585},{6,8498459},{7,1722776}, > {7,3389380},{7,4313727},{7,5466169}}} > > So, the digit 9 occurs at most 7 times in a row. > > This is more in line with your specific length example. > This does not look at overlap: > > DigitSequence2[s_,d_,length_]:=Module[ > {z,t}, > z=StringReplace["n{s,s}",{"n"->ToString[d],"s"->ToString[length]}]; > t=StringPosition[s,RegularExpression[z],Overlaps->False]; > t/.{x_Integer,y_Integer}:>x > ] > > DigitSequence2[pi,9,7]//Timing > {0.08325,{1722776,3389380,4313727,5466169}} > > = = = = = = = = = = > HTH : >) > Dana DeLouis > $Version > 8.0 for Mac OS X x86 (64-bit) (November 6, 2010) > > On Jun 10, 6:38 am, Guillermo Sanchez <guillermo.sanc... at hotmail.com> wrote: > > > > > > > > > Dear Group > > > I have developed this function > > > piesimo[n_, m_, r_] := Module[{a}, a = Split[RealDigits[Pi - 3, 10, n] > > [[1]]]; Part[Accumulate[Length /@ a], Flatten[Position[a, Table[m, > > {r}]]] - 1] + 1] > > > n is the digits of Pi, after 3, where to search a sequence of m digit > > r times consecutives. > > For instance: > > > piesimo[10^7, 9, 7] > > > Gives that the sequence 9999999 happens in positions: > > > {1722776, 3389380, 4313727, 5466169} > > > I know that in this group I will find faster methods. Any idea? > > > Guillermo Well, it looks like the increased speed is due to the use of RegularExpression. I modified piesimoS is: piesimoSR[m_String] := First /@ StringPosition[pi, RegularExpression[m], Overlaps -> False] DigitSequence[pi, 9, 7] // Timing {0.076988, {{7, 1722776}, {7, 3389380}, {7, 4313727}, {7, 5466169}}} piesimoS["9999999"] // Timing {0.204969, {1722776, 3389380, 4313727, 5466169}} piesimoSR["9999999"] // Timing {0.072989, {1722776, 3389380, 4313727, 5466169}}