login
First primitive GF(2)[X] polynomial of degree n.
6

%I #30 Mar 29 2024 06:15:03

%S 3,7,11,19,37,67,131,285,529,1033,2053,4179,8219,16427,32771,65581,

%T 131081,262183,524327,1048585,2097157,4194307,8388641,16777243,

%U 33554441,67108935,134217767,268435465,536870917,1073741907,2147483657

%N First primitive GF(2)[X] polynomial of degree n.

%H Robert Israel, <a href="/A132447/b132447.txt">Table of n, a(n) for n = 1..330</a>

%H Rich Schroeppel, <a href="http://richard.schroeppel.name:8015/hpc/hpc-spec">Hasty Pudding Cipher Specification on archive.org</a>, (revised May 1999 ed.), June 1998. (The numbers are called "Swizpoly numbers" here, except that they start with 0 for some reason.)

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>

%e a(5)=37, or 100101 in binary, representing the GF(2)[X] polynomial X^5+X^2+1, because it has degree 5 and is primitive, contrary to X^5, X^5+1, X^5+x^1, X^5+X^1+1 and X^5+X^2.

%p f:= proc(n) local k,L,i,X;

%p for k from 2^n+1 by 2 do

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

%p if Primitive(add(L[i]*X^(i-1),i=1..n+1)) mod 2 then return k fi

%p od

%p end proc:

%p map(f, [$1..40]); # _Robert Israel_, Nov 05 2023

%t f[n_] := If[n == 1, 3, Module[{k, L, i, X}, For[k = 2^n+1, True, k = k+2, L = IntegerDigits[k, 2]; If[PrimitivePolynomialQ[Sum[L[[i]]*X^(i-1), {i, 1, n+1}], 2], Return[k]]]]];

%t Table[f[n], {n, 1, 40}] (* _Jean-François Alcover_, Mar 29 2024, after _Robert Israel_ *)

%Y a(n) is the smallest member of A091250 at least 2^n. A132448(n) = a(n)-2^n, giving a more compact representation. Cf. A132449, similar, with restriction to at most 5 terms. Cf. A132451, similar, with restriction to exactly 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

%K nonn

%O 1,1

%A _Francois R. Grieu_, Aug 22 2007