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

1, 1, 3, 8, 14, 32, 60, 128, 248, 512, 1008, 2048, 4064, 8192, 16320, 32768, 65408, 131072, 261888, 524288, 1048064, 2097152, 4193280, 8388608, 16775168, 33554432, 67104768, 134217728, 268427264

Offset: 0

Author

Peter Kagey, Jan 03 2022

Keywords

• nonn
• more

Examples

			For n = 2, there are a(2) = 3 degree 4 polynomials of the form f(f(x)):
  x^4         = f(f(x)) when f(x) = x^2 or f(x) = x^2 + 1,
  x^4 + x     = f(f(x)) when f(x) = x^2 + x, and
  x^4 + x + 1 = f(f(x)) when f(x) = x^2 + x + 1.
		

Crossrefs

Cf. A033991, A156212, A156232.

Formula

Conjecture:

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

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

Conjecture from Hugo Pfoertner, Jan 09 2022: Terms starting at 3 coincide with {A156232}/8.

Extensions

a(0) prepended and a(11)-a(28) from Martin Ehrenstein, Jan 14 2022