A376932 a(n) is the index of the first GF(2)[X] polynomial that has n distinct irreducible factors.

1, 2, 6, 18, 166, 1806, 20382, 272706, 8323326, 158143194, 4319806194, 139715547110, 4563596609414, 154716297384250, 6051527318503338, 315946019303255670, 18477283150919171654, 1191953715632050834242, 76457609628854745786262, 4838004466153152832995822, 312401901306255000752991994, 20039165126917559409941672886

Offset

0,2

Comments

a(n) is the least k such that A091221(k) = n.

Links

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

Example

a(3) = 18 because the 18th GF(2)[X] polynomial is X^4 + X = X * (X + 1) * (X^2 + X + 1) with 3 distinct irreducible factors over GF(2).

Maple

pol:= proc(x) local L, i;
  L:= convert(x, base, 2);
  add(L[i]*X^(i-1), i=1..nops(L));
end proc:
for m from 1 to 10 do
  IP[m]:= select(t -> Irreduc(pol(t)) mod 2, [seq(x, x=2^m..2^(m+1)-1)]);
od:
nIP:= [seq(nops(IP[m]), m=1..10)]:
psnIP:= ListTools:-PartialSums(nIP):
f:= proc(n) local k, P0, r, xmin, x, i, s, P;
  for k from 1 while n > psnIP[k] do od:
  P0:= expand(mul(convert(map(pol, IP[i]), `*`), i=1..k-1)) mod 2;
  if k = 1 then r:= n else r:= n - psnIP[k-1] fi;
  xmin:= infinity;
  for s in combinat:-choose(IP[k], r) do
    P:= expand(P0 * mul(pol(i), i=s)) mod 2;
    x:= eval(P, X=2);
    xmin:= min(xmin, x);
  od;
  xmin
end proc:
seq(f(i), i=0..25);

Crossrefs

Cf. A091221.

Sequence in context: A308549 A212653 A323104 * A208456 A056743 A064535

Adjacent sequences: A376929 A376930 A376931 * A376933 A376934 A376935

Keyword

nonn

Author

Robert Israel, Oct 11 2024

Status

approved