Counter example to LCFF.sagews

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]