Skip to content

Instantly share code, notes, and snippets.

@PRotondo
Created August 13, 2014 15:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save PRotondo/0376dfd3405a59468940 to your computer and use it in GitHub Desktop.
Save PRotondo/0376dfd3405a59468940 to your computer and use it in GitHub Desktop.
Fast look-and-say computation (for the binary case, starting with 0), implemented in Sage.
import itertools
M = {}
def look_and_say(atom,n) :
global M
a = atom
if n == 0 :
return 0
b = ""
for c,l in itertools.groupby(a) :
b += bin(len(list(l)))[2:] + c
if n == 1 :
return len(b)
P = (atom,n)
if P in M :
return M[P]
a = b + "2"
start = 0
prev = False
atom = ""
ans = 0
for j,s in enumerate(a) :
if s == "1" and prev :
ans += look_and_say(a[start:j],n-1)
start = j
prev = False
elif s == "0" :
prev = True
elif s == "2" :
ans += look_and_say(a[start:j],n-1)
M[P] = ans
return ans
R = RealField(1000)
print R(look_and_say("0",700)) / R(look_and_say("0",699))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment