A376932 - OEIS

%I #6 Oct 13 2024 11:20:25

%S 1,2,6,18,166,1806,20382,272706,8323326,158143194,4319806194,

%T 139715547110,4563596609414,154716297384250,6051527318503338,

%U 315946019303255670,18477283150919171654,1191953715632050834242,76457609628854745786262,4838004466153152832995822,312401901306255000752991994,20039165126917559409941672886

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

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

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

%p pol:= proc(x) local L,i;

%p   L:= convert(x,base,2);

%p   add(L[i]*X^(i-1),i=1..nops(L));

%p end proc:

%p for m from 1 to 10 do

%p   IP[m]:= select(t -> Irreduc(pol(t)) mod 2, [seq(x,x=2^m..2^(m+1)-1)]);

%p od:

%p nIP:= [seq(nops(IP[m]),m=1..10)]:

%p psnIP:= ListTools:-PartialSums(nIP):

%p f:= proc(n) local k,P0,r, xmin, x, i, s, P;

%p   for k from 1 while n > psnIP[k] do od:

%p   P0:= expand(mul(convert(map(pol,IP[i]),`*`),i=1..k-1)) mod 2;

%p   if k = 1 then r:= n else r:= n - psnIP[k-1] fi;

%p   xmin:= infinity;

%p   for s in combinat:-choose(IP[k],r) do

%p     P:= expand(P0 * mul(pol(i),i=s)) mod 2;

%p     x:= eval(P,X=2);

%p     xmin:= min(xmin, x);

%p   od;

%p   xmin

%p end proc:

%p seq(f(i),i=0..25);

%Y Cf. A091221.

%K nonn

%O 0,2

%A _Robert Israel_, Oct 11 2024