def monicpoly(n, d) : """return, as a list of coefficients, constant term last, nth height 1 monic polynomial of degree d with nonzero constant term""" n, r = divmod(n, 2) p = [2*r-1] for _ in range(d-1) : n, r = divmod(n, 3) p.append(r-1) if n : raise ValueError('n too big') p.append(1) p.reverse() return p def height1(d) : """generate all* monic height 1 polys p of degree d with p(x) != 0 polys are returned in lexicographical increasing or decreasing order *If a poly has a lexicographically less equivalent, skip it.""" if d < 2 : yield [1, -1] if d else [1] return for n in range(4*3**(d-2)) : p = monicpoly(n, d) # see if there are lexicographically less equivalents c = 0 for i in range(1, d+1, 2) : if not p[i] : continue c = p[i] > 0 break if c : continue # x->-x (but monic) is lexicographically less if p[-1] > 0 : for i in range(1, d//2+1) : if p[i] == p[d-i] : continue c = p[i] > p[d-i] break if c : continue # x->1/x (but monic) is lexicographically less for i in range(1, d, 2) : if p[i] != -p[d-i] : c = p[i] > -p[d-i] break if p[i+1] == p[d-i-1] : continue c = p[i+1] > p[d-i-1] break else : for i in range(1, d//2+1) : if p[i] == -p[d-i] : continue c = p[i] > -p[d-i] break if c : continue # x->1/x (but monic) is lexicographically less for i in range(1, d, 2) : if p[i] != p[d-i] : c = p[i] > p[d-i] break if p[i+1] == -p[d-i-1] : continue c = p[i+1] > -p[d-i-1] break if c : continue # x->-1/x (but monic) is lexicographically less yield p def a(n) : c = 0 for p in height1(n) : c+=1 return c