CoCalc Shared FilesCounter example to LCFF.sagews
Author: Erez Nesharim
Views : 113
def Dragon(n):
"""
This function returns the nth element of the dragon sequence
"""
if n == 0:
return 0
else:
while Mod(n, 2) == 0:
#while n%2 == 0:
n = n / 2
return ((n-1)/2)%2

def Dragon2(n):
"""
This function returns the 2nth element of the dragon sequence
"""
return Dragon(2*n)

def Pagoda(n):
"""
This function returns the nth element of the pagoda sequence
"""
return Dragon(n+1) - Dragon(n-1)

def GoldenSection(n):
"""
This function returns the nth element of the golden section sequence
It gol_{2n} = 0 and gol_{2n+1} = (-1)^{n+1} * catalan_number(n)
"""
if n%2==0:
return 0
else:
return catalan_number((n-1)/2)*(1 - (n-1)%4)

def plot_labels(x_ticks,x_labels,y_ticks,y_labels,fontsize=12):
import matplotlib.ticker
def latex_ticklabels(lbls_x,lbls_y):
return [matplotlib.ticker.FixedFormatter(lbls_x),matplotlib.ticker.FixedFormatter(lbls_y)]
ft=fontsize
return plot([],ticks=[x_ticks,y_ticks],tick_formatter=latex_ticklabels(x_labels,y_labels),fontsize=ft)

def fibonaci_poly(n,k,char=0):
"""
This function returns the vector of coefficients of the
kth coefficient of the nth fibonacci polynomial of degree n
F(n,k) modulo char, which is set to be 0 by default.
Fibonacci polynomials are defined recursively by
q_n(t) = t*q_{n-1}(t) + q_{n-2}(t)
and we use the formula F(n,k)=binomial((n+k-1)/2,k)
"""
if Mod(n,2)==Mod(k,2):
return 0
else:
return Mod(binomial((n+k-1)/2,k),char)

print([Mod(catalan_number(n),2) for n in range (1,300)])
print([Mod(catalan_number(n),3) for n in range (1,300)])

[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 2, 2, 2, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
import time
start = time.time()

M = 170
leng = 2*M
char = 3
pag = [Mod(Pagoda(n),char) for n in range (1,leng)]
#rpf = [Dragon(n) for n in range (1,leng)]
#gol = [Mod(GoldenSection(n),char) for n in range (1,leng)]
par = [Mod(Pagoda(-n),char) for n in range (1,leng)]

table = [[0 for j in range(0,m+1)] for m in range(1,M+1)]
for m in range(1,M+1):
tempMat = [[0 for j in range(0,m)] for n in range(0,m)]
for h in range(0,m+1):
for j in range(0,h):
#print(j,h,m,"here")
#tempMat[j] = [rpf[j + n] for n in range(0,m)]
tempMat[j] = [pag[j + n] for n in range(0,m)]
for j in range(h,m):
#print(j,h,m,"there")
tempMat[j] = [par[j - h - 1 + n] for n in range(0,m)]
table[m-1][h] = Mod(matrix(tempMat).det(),char)

end = time.time()
print(end - start)
P=plot_labels([],[],[],[])
for c in range(0,char):
rgb=(char-1-c%char)/(char-1)
P=P+points([(1+j,-m) for m in range(0,M) for j in range(0,m+1) if table[m][j]==mod(c,char)],color=Color(rgb,rgb,rgb),marker='s')

P.axes_color('white')
P.show()

end = time.time()
print(end - start)

Error in lines 9-16 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1191, in execute flags=compile_flags), namespace, locals) File "", line 7, in <module> File "src/cysignals/signals.pyx", line 320, in cysignals.signals.python_check_interrupt KeyboardInterrupt
import time
start = time.time()

M = 200
leng = 2*M
char = 3
pag = [Mod(Pagoda(n),char) for n in range (1,leng)]
#rpf = [Dragon(n) for n in range (1,leng)]
#gol = [Mod(GoldenSection(n),char) for n in range (1,leng)]
cat = [Mod(catalan_number(n),char) for n in range (1,leng)]

table = [[0 for j in range(0,m+1)] for m in range(1,M+1)]
for m in range(1,M+1):
tempMat = [[0 for j in range(0,m)] for n in range(0,m)]
for h in range(0,m+1):
for j in range(0,h):
#print(j,h,m,"here")
#tempMat[j] = [rpf[j + n] for n in range(0,m)]
tempMat[j] = [pag[j + n] for n in range(0,m)]
for j in range(h,m):
#print(j,h,m,"there")
tempMat[j] = [cat[j - h + n] for n in range(0,m)]
table[m-1][h] = Mod(matrix(tempMat).det(),char)

end = time.time()
print(end - start)

#calculate defficiencies
defs = [[0 for j in range(0,m+1)] for m in range(1,M+1)]
for m in range (M,0,-1): #start counting from the bottom
for j in range (0,m+1):
if table[m-1][j] != 0:
defs[m-1][j] = 0
else:
if m == M:
defs[m-1][j] = 1
else:
defs[m-1][j] = max(defs[m][j],defs[m][j+1]) + 1

print([max(defs[m-1]) for m in range(1,M+1)])

P=plot_labels([],[],[],[])
for c in range(0,char):
rgb=(char-1-c%char)/(char-1)
P=P+points([(1+j,-m) for m in range(1,M+1) for j in range(0,m+1) if table[m-1][j]==mod(c,char)],color=Color(rgb,rgb,rgb),marker='s')

P.axes_color('white')
P.show()

end = time.time()
print(end - start)

1145.0585959 [1, 0, 4, 3, 2, 1, 1, 1, 7, 6, 5, 4, 3, 2, 4, 3, 2, 7, 9, 8, 7, 6, 5, 4, 4, 4, 5, 4, 3, 2, 3, 13, 12, 11, 10, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 10, 9, 8, 7, 6, 5, 9, 8, 7, 11, 10, 9, 8, 7, 6, 8, 7, 6, 5, 5, 4, 5, 8, 9, 16, 15, 14, 13, 12, 11, 10, 9, 8, 10, 9, 8, 7, 6, 5, 4, 4, 4, 3, 10, 9, 8, 7, 6, 5, 6, 12, 11, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 7, 6, 7, 6, 7, 10, 9, 8, 12, 11, 10, 9, 8, 9, 8, 22, 21, 20, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 13, 12, 11, 14, 13, 12, 11, 10, 9, 8, 7, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 13, 12, 11, 10, 9, 10, 9, 8, 9, 8, 7, 6, 5, 12, 11, 12, 11, 10, 9, 11, 10, 9, 8, 7, 6, 9, 8, 7, 6, 5, 4, 3, 2, 1]
1150.42876387
import time
start = time.time()

M = 600
leng = 2*M
char = 3
weight = 1/2

pag = [Mod(Pagoda(n),char) for n in range (1,leng)]
#rpf = [Dragon(n) for n in range (1,leng)]
#gol = [Mod(GoldenSection(n),char) for n in range (1,leng)]
cat = [Mod(catalan_number(n),char) for n in range (1,leng)]

end = time.time()
print(end - start)

dets = [0 for m in range(1,M+1)]
for m in range(1,M+1):
tempMat = [[0 for j in range(0,m)] for n in range(0,m)]
h = round(weight*m)
for j in range(0,h):
tempMat[j] = [pag[j + n] for n in range(0,m)]
for j in range(h,m):
tempMat[j] = [cat[j - h + n] for n in range(0,m)]
dets[m-1] = Mod(matrix(tempMat).det(),char)

print(dets)

defs = [0 for m in range(1,M+1)]
for m in range (M,0,-1): #start counting from the bottom
if dets[m-1] != 0:
defs[m-1] = 0
else:
if m == M:
defs[m-1] = 1
else:
defs[m-1] = defs[m] + 1

print(defs)
print(max(defs))

end = time.time()
print(end - start)

0.205230951309 [0, 2, 0, 0, 0, 0, 1, 0, 2, 2, 0, 0, 0, 2, 2, 0, 2, 0, 2, 2, 0, 0, 2, 2, 2, 0, 0, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 0, 0, 2, 1, 1, 0, 2, 2, 0, 0, 2, 0, 2, 1, 1, 2, 0, 0, 1, 0, 1, 2, 2, 2, 2, 0, 2, 0, 1, 1, 2, 2, 1, 0, 2, 0, 0, 0, 1, 1, 1, 0, 1, 0, 2, 2, 0, 0, 1, 1, 2, 0, 2, 1, 2, 1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 0, 2, 2, 2, 0, 0, 1, 0, 1, 0, 2, 2, 2, 2, 1, 0, 0, 1, 2, 0, 2, 0, 0, 1, 2, 2, 2, 1, 2, 0, 1, 2, 2, 1, 0, 1, 1, 2, 1, 0, 0, 0, 1, 2, 0, 1, 0, 1, 2, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 2, 2, 2, 0, 2, 2, 2, 0, 0, 1, 2, 1, 2, 1, 1, 2, 2, 0, 0, 1, 2, 0, 0, 0, 0, 1, 2, 0, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 1, 2, 1, 0, 2, 2, 2, 2, 1, 1, 0, 2, 0, 1, 0, 0, 1, 2, 2, 1, 0, 0, 2, 1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 2, 2, 2, 0, 0, 1, 1, 1, 0, 0, 2, 2, 0, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 0, 0, 2, 0, 0, 0, 2, 1, 1, 2, 1, 2, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 2, 2, 1, 1, 0, 1, 2, 2, 1, 2, 2, 1, 0, 1, 1, 1, 2, 2, 2, 1, 0, 0, 1, 1, 0, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 2, 1, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 0, 0, 0, 0, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 0, 0, 2, 2, 1, 0, 1, 2, 1, 2, 0, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 2, 1, 1, 2, 2, 1, 1, 0, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 2, 2, 2, 2, 1, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 1, 2, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 1, 0, 1, 0, 2, 2, 0, 1, 1, 2, 2, 2, 2, 1, 0, 2, 1, 1, 1, 0, 0, 0, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 0, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 0, 0, 2, 1, 1, 0, 1, 1, 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 2, 2, 2, 2, 0] [1, 0, 4, 3, 2, 1, 0, 1, 0, 0, 3, 2, 1, 0, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 3, 2, 1, 0, 0, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 3, 2, 1, 0, 2, 1, 0, 0, 1, 0, 1, 0, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 4, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 3, 2, 1, 0, 1, 0, 0, 0, 6, 5, 4, 3, 2, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 3, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 6, 5, 4, 3, 2, 1, 0, 2, 1, 0, 0, 0, 0, 3, 2, 1, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 4, 3, 2, 1, 0, 0, 1, 0, 0, 3, 2, 1, 0, 0, 0, 1, 0, 0, 0, 5, 4, 3, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 1] 8 654.19997406

m)]
tempMat[j] = [pag[j + n] for n in range(0,m)]
for j in range(h,m):
#print(j,h,m,"there")
tempMat[j] = [cat[j - h + n] for n in range(0,m)]
table[m-1][h] = Mod(matrix(tempMat).det(),char)

end = time.time()
print(end - start)

#calculate defficiencies
defs = [[0 for j in range(0,m+1)] for m in range(1,M+1)]
for m in range (M,0,-1): #start counting from the bottom
for j in range (0,m+1):
if table[m-1][j] != 0:
defs[m-1][j] = 0
else:
if m == M:
defs[m-1][j] = 1
else:
defs[m-1][j] = max(defs[m][j],defs[m][j+1]) + 1

print([max(defs[m-1]) for m in range(1,M+1)])

P=plot_labels([],[],[],[])
for c in range(0,char):
rgb=(char-1-c%char)/(char-1)
P=P+points([(1+j,-m) for m in range(1,M+1) for j in range(0,m+1) if table[m-1][j]==mod(c,char)],color=Color(rgb,rgb,rgb),marker='s')

P.axes_color('white')
P.show()

end = time.time()
print(end - start)

1145.0585959 [1, 0, 4, 3, 2, 1, 1, 1, 7, 6, 5, 4, 3, 2, 4, 3, 2, 7, 9, 8, 7, 6, 5, 4, 4, 4, 5, 4, 3, 2, 3, 13, 12, 11, 10, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 10, 9, 8, 7, 6, 5, 9, 8, 7, 11, 10, 9, 8, 7, 6, 8, 7, 6, 5, 5, 4, 5, 8, 9, 16, 15, 14, 13, 12, 11, 10, 9, 8, 10, 9, 8, 7, 6, 5, 4, 4, 4, 3, 10, 9, 8, 7, 6, 5, 6, 12, 11, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 7, 6, 7, 6, 7, 10, 9, 8, 12, 11, 10, 9, 8, 9, 8, 22, 21, 20, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 13, 12, 11, 14, 13, 12, 11, 10, 9, 8, 7, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 13, 12, 11, 10, 9, 10, 9, 8, 9, 8, 7, 6, 5, 12, 11, 12, 11, 10, 9, 11, 10, 9, 8, 7, 6, 9, 8, 7, 6, 5, 4, 3, 2, 1]
1150.42876387
import time
start = time.time()

M = 600
leng = 2*M
char = 3
pag = [Mod(Pagoda(n),char) for n in range (1,leng)]
#rpf = [Dragon(n) for n in range (1,leng)]
#gol = [Mod(GoldenSection(n),char) for n in range (1,leng)]
cat = [Mod(catalan_number(n),char) for n in range (1,leng)]

end = time.time()
print(end - start)

dets = [0 for m in range(1,M+1)]
for m in range(1,M+1):
tempMat = [[0 for j in range(0,m)] for n in range(0,m)]
h = round(weight*m)
for j in range(0,h):
tempMat[j] = [pag[j + n] for n in range(0,m)]
for j in range(h,m):
tempMat[j] = [cat[j - h + n] for n in range(0,m)]
dets[m-1] = Mod(matrix(tempMat).det(),char)

print(dets)

defs = [0 for m in range(1,M+1)]
for m in range (M,0,-1): #start counting from the bottom
if dets[m-1] != 0:
defs[m-1] = 0
else:
if m == M:
defs[m-1] = 1
else:
defs[m-1] = defs[m] + 1

print(defs)
print(max(defs))

end = time.time()
print(end - start)

0.205230951309 [0, 2, 0, 0, 0, 0, 1, 0, 2, 2, 0, 0, 0, 2, 2, 0, 2, 0, 2, 2, 0, 0, 2, 2, 2, 0, 0, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 0, 0, 2, 1, 1, 0, 2, 2, 0, 0, 2, 0, 2, 1, 1, 2, 0, 0, 1, 0, 1, 2, 2, 2, 2, 0, 2, 0, 1, 1, 2, 2, 1, 0, 2, 0, 0, 0, 1, 1, 1, 0, 1, 0, 2, 2, 0, 0, 1, 1, 2, 0, 2, 1, 2, 1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 0, 2, 2, 2, 0, 0, 1, 0, 1, 0, 2, 2, 2, 2, 1, 0, 0, 1, 2, 0, 2, 0, 0, 1, 2, 2, 2, 1, 2, 0, 1, 2, 2, 1, 0, 1, 1, 2, 1, 0, 0, 0, 1, 2, 0, 1, 0, 1, 2, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 2, 2, 2, 0, 2, 2, 2, 0, 0, 1, 2, 1, 2, 1, 1, 2, 2, 0, 0, 1, 2, 0, 0, 0, 0, 1, 2, 0, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 1, 2, 1, 0, 2, 2, 2, 2, 1, 1, 0, 2, 0, 1, 0, 0, 1, 2, 2, 1, 0, 0, 2, 1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 2, 2, 2, 0, 0, 1, 1, 1, 0, 0, 2, 2, 0, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 0, 0, 2, 0, 0, 0, 2, 1, 1, 2, 1, 2, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 2, 2, 1, 1, 0, 1, 2, 2, 1, 2, 2, 1, 0, 1, 1, 1, 2, 2, 2, 1, 0, 0, 1, 1, 0, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 2, 1, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 0, 0, 0, 0, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 0, 0, 2, 2, 1, 0, 1, 2, 1, 2, 0, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 2, 1, 1, 2, 2, 1, 1, 0, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 2, 2, 2, 2, 1, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 1, 2, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 1, 0, 1, 0, 2, 2, 0, 1, 1, 2, 2, 2, 2, 1, 0, 2, 1, 1, 1, 0, 0, 0, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 0, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 0, 0, 2, 1, 1, 0, 1, 1, 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 2, 2, 2, 2, 0] [1, 0, 4, 3, 2, 1, 0, 1, 0, 0, 3, 2, 1, 0, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 3, 2, 1, 0, 0, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 3, 2, 1, 0, 2, 1, 0, 0, 1, 0, 1, 0, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 4, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 3, 2, 1, 0, 1, 0, 0, 0, 6, 5, 4, 3, 2, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 3, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 6, 5, 4, 3, 2, 1, 0, 2, 1, 0, 0, 0, 0, 3, 2, 1, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 4, 3, 2, 1, 0, 0, 1, 0, 0, 3, 2, 1, 0, 0, 0, 1, 0, 0, 0, 5, 4, 3, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 1] 8 654.19997406
import time
start = time.time()

M = 1000
leng = 2*M
char = 3

pag = [Pagoda(n) for n in range (1,leng)]
pag_def = 1

defs_along_convergents = [0 for m in range(1,M+1)]
for m in range(1,M+1):
i=0
fib_m = [fibonaci_poly(m,n,char) for n in range(0,m)]
while i < m + pag_def and sum([pag[i + n]*fib_m[n] for n in range(0,m)])%char==0:
i += 1
defs_along_convergents[m-1] = i

print(defs_along_convergents)
print(max(defs_along_convergents))

end = time.time()
print(end - start)

[1, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 0, 1, 0, 0, 2, 0, 1, 3, 1, 0, 0, 0, 1, 7, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 4, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 4, 0, 1, 5, 1, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 6, 0, 1, 3, 1, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 4, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 4, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 4, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 0, 3, 0, 0, 0, 0, 1, 1, 0, 0, 6, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 1, 1, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 6, 0, 1, 1, 0, 0, 2, 0, 0, 7, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 2, 0, 0, 5, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 2, 0, 1, 1, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 3, 1, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 6, 0, 0, 1, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 7, 1, 0, 0, 0, 0, 1, 1, 0, 2, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 6, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 5, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 6, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 6, 0, 0, 1, 0, 0, 4, 0, 0, 1, 1, 0, 2, 0, 0, 1, 0, 0, 4, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 11, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 1, 0, 0, 2, 0] 11 25.9435641766
import time
start = time.time()

M = 100
leng = 2*M
char = 3
rpf = [Mod(Dragon(n),char) for n in range (1,leng)]
rpf2 = [Mod(Dragon(2*n-1),char) for n in range (1,leng)]
table = [[0 for j in range(0,m+1)] for m in range(1,M+1)]
for m in range(1,M+1):
tempMat = [[0 for j in range(0,m)] for n in range(0,m)]
for h in range(0,m+1):
for j in range(0,h):
#print(j,h,m,"here")
#tempMat[j] = [rpf[j + n] for n in range(0,m)]
tempMat[j] = [rpf[j + n] for n in range(0,m)]
for j in range(h,m):
#print(j,h,m,"there")
tempMat[j] = [rpf2[j - h - 1 + n] for n in range(0,m)]
table[m-1][h] = Mod(matrix(tempMat).det(),char)

end = time.time()
print(end - start)
P=plot_labels([],[],[],[])
for c in range(0,char):
rgb=(char-1-c%char)/(char-1)
P=P+points([(1+j,-m) for m in range(0,M) for j in range(0,m+1) if table[m][j]==mod(c,char)],color=Color(rgb,rgb,rgb),marker='s')

P.axes_color('white')
P.show()

end = time.time()
print(end - start)

67.6483972073
69.0173401833


rpf2 = [Mod(Dragon(2*n),char) for n in range (1,leng)]
print(rpf2)

[0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1]