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

Author

Robert Israel, Oct 11 2024

Keywords

• nonn

Comments

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

Examples

			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).
		

Crossrefs

Cf. A091221.

Programs

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);