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,3

Links

Table of n, a(n) for n=0..28.

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.

Example

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.

Sequence in context: A129067 A298612 A340627 * A168155 A005735 A208436

Adjacent sequences: A350517 A350518 A350519 * A350521 A350522 A350523

Keyword

nonn,more

Author

Peter Kagey, Jan 03 2022

Extensions

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

Status

approved