# A055547: 2, 8, 68, ... # # 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 = [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)]