login
The number of degree-n^2 polynomials over Z/2Z that can be written as f(f(x)) where f is a polynomial.
0

%I #24 Jan 14 2022 07:35:58

%S 1,1,3,8,14,32,60,128,248,512,1008,2048,4064,8192,16320,32768,65408,

%T 131072,261888,524288,1048064,2097152,4193280,8388608,16775168,

%U 33554432,67104768,134217728,268427264

%N The number of degree-n^2 polynomials over Z/2Z that can be written as f(f(x)) where f is a polynomial.

%F Conjecture:

%F a(2n) = A033991(2^(n-1)) = 4^n - 2^(n-1) for n >= 1;

%F a(2n+1) = 2^(2n+1) for n >= 1.

%F Conjecture from _Hugo Pfoertner_, Jan 09 2022: Terms starting at 3 coincide with {A156232}/8.

%e For n = 2, there are a(2) = 3 degree 4 polynomials of the form f(f(x)):

%e x^4 = f(f(x)) when f(x) = x^2 or f(x) = x^2 + 1,

%e x^4 + x = f(f(x)) when f(x) = x^2 + x, and

%e x^4 + x + 1 = f(f(x)) when f(x) = x^2 + x + 1.

%Y Cf. A033991, A156212, A156232.

%K nonn,more

%O 0,3

%A _Peter Kagey_, Jan 03 2022

%E a(0) prepended and a(11)-a(28) from _Martin Ehrenstein_, Jan 14 2022