|
%I #19 Jul 31 2015 18:05:43
%S 1,3,9,404,6355,11482910373,1268361281038
%N Number of polynomials P = Sum_{k=0..m} x^{d(k)} with 0 = d(0) < ... < d(m) and P^2 = Sum_{k>=0} B(k) x^k such that B(k) <= n for all k and B(k) > 0 for k <= d(m).
%H Peter Borwein, Stephen Choi and Frank Chu, <a href="http://dx.doi.org/10.1090/S0025-5718-05-01777-1">An old conjecture of Erdos-Turán on additive bases</a>, Math. Comp. 75 (2006), 475-484, see Table 1 p. 481.
%e For n=1, the only possible polynomial is P = 1 (the coefficient of x^0 must always be 1), and its square P^2 = 1 satisfies the conditions. If another term is added, there will be a coefficient 2 > n in the square, which is forbidden.
%e For n=2, the 3 polynomials are {1, x+1, x^3+x+1}. P = x^2+1 is excluded because P^2 has a zero coefficient for x^1. P = x^2+x+1 is excluded because P^2 has a coefficient 3 > n which is forbidden. If the degree is > 3, then either there will be a zero coefficient in P^2 below deg(P), or there will be a coefficient > 2.
%e For n=3, the 9 polynomials are {1, x+1, x^2+x+1, x^3+x+1, x^4+x^2+x+1, x^5+x^2+x+1, x^5+x^3+x+1, x^7+x^4+x^2+x+1, x^8+x^5+x^2+x+1}.
%o (PARI) A260551(n,c=1,L=2<<[1,3,8,40,52,264,328][n])={c||c=[1]; forstep(i=2,L,2,normlp(P2=Pol(binary(1+i))^2)>n&&next; for(k=1,#binary(i),component(P2,k)||next(2));if(type(c)!="t_INT",c=concat(c,Pol(binary(1+i))),c++));c} \\ Use 2nd arg=0 or [] to get the list of polynomials. For n>3 this code takes too long, but you may give a lower limit as 3rd arg to get quickly a list of the first 200-300 solutions. - _M. F. Hasler_, Jul 31 2015
%K nonn,more
%O 1,2
%A _Michel Marcus_, Jul 29 2015
%E Definition and examples clarified by _M. F. Hasler_, Jul 31 2015
|
