# A055549: 3, 33, 939, ...
#
# The code below computes the higher entries in these sequences quickly,
# by recursively adding rows and columns. Rows r_i, r_j and columns
# c_i, c_j for which the inner products <r_i, r_j> and <c_i, c_j> are
# not equal, can then be discarded at an early stage. To speed things up,
# the top three functions can be precompiled using Cython.

%cython
def ip(v1, v2):
    return sum([v1[i]*v2[i] for i in range(len(v1))])

def ips(Lr, Lc):
    flag = True
    i = 0
    while flag and i <= len(Lr) - 1:
        if ip(Lr[i], Lr[-1]) != ip(Lc[i], Lc[-1]):
            return False
        i += 1
    return True

def rc(Ltup, n):
    m = len(Ltup)
    r = [Ltup[i][n-m] for i in range(m-1)] + Ltup[-1][n-m:]
    c = Ltup[-1][:n-m+1] + [ Ltup[m-2-i][n+2-m+2*i] for i in range(m-1) ]
    c.reverse()
    return r, c

%sage
entries = [-1, 0, 1]
def NrMat(Ltup, Lr, Lc, n):
    if ips(Lr, Lc):
        m = len(Lc)
        if m == n:
            return 1
        else:
            N = 0
            L0 = [entries for i in range(2*n - 1 - 2*m)]
            for tup in cartesian_product_iterator(L0):
                Ltup1 = Ltup + [list(tup)]
                r, c = rc(Ltup1, n)
                N += NrMat(Ltup1, Lr + [r], Lc + [c], n)

            return N
    return 0

print [NrMat([], [], [], n) for n in range(1, 4)]