[Date Index] [Thread Index] [Author Index]

Re: Seaching in Pi a sequence. Looking for a faster method

• To: mathgroup at smc.vnet.net
• Subject: [mg119593] Re: Seaching in Pi a sequence. Looking for a faster method
• From: Anthony Hodsdon <ajhodsd at hotmail.com>
• Date: Sat, 11 Jun 2011 06:49:35 -0400 (EDT)
• References: <201106101038.GAA19889@smc.vnet.net> <05cf01cc27fd$271fb3e0$755f1ba0$@hotmail.com>

Actually, come to think of it, I think the biggest benefit of the string
approach is the reduction in memory used:

In[72]:= ToString[N[Pi - 3, 10^7]] // ByteCount

Out[72]= 10000048

In[75]:= Split[RealDigits[Pi - 3, 10, 10^7][[1]]] // ByteCount

Out[75]= 751990872

--Anthony

-----Original Message-----
From: Anthony Hodsdon [mailto:ajhodsd at hotmail.com] 
Sent: Friday, June 10, 2011 11:02 PM
To: 'Guillermo Sanchez'; 'mathgroup at smc.vnet.net'
Subject: [mg119593] Re: Seaching in Pi a sequence. Looking for a faster
method

This sounds like a job for string search:

piesimo2[n_, m_, r_] := 
 Transpose[
   StringPosition[StringDrop[ToString[N[Pi, n]], 2], 
    ToString[m*(10^r - 1)/9]]][[1]]

In[44]:= piesimo2[10^7, 9, 7] // Timing

Out[44]= {19.063, {1722776, 3389380, 4313727, 5466169}}

Not bad, considering "stringifying" pi to begin with seems to take most of
the time:

In[49]:= ToString[N[Pi, 10^7]]; // Timing

Out[49]= {18.19, Null}

Mathematica can do the actual search very quickly using a linear time (in
terms of n+r) algorithm (see, for instance,
http://en.wikipedia.org/wiki/String_searching_algorithm).

--Anthony

-----Original Message-----
From: Guillermo Sanchez [mailto:guillermo.sanchez at hotmail.com] 
Sent: Friday, June 10, 2011 3:38 AM
To: mathgroup at smc.vnet.net
Subject: [mg119593] Seaching in Pi a sequence. Looking for a faster method

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

• References:
  • Seaching in Pi a sequence. Looking for a faster method
    • From: Guillermo Sanchez <guillermo.sanchez@hotmail.com>