login
Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).
0

%I #41 Oct 14 2023 21:15:57

%S 0,1,2,10,29,265,449,682

%N Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).

%C An integer k > 1 belongs to this sequence iff A100730(k) = 2^(2k+3) - 2.

%C Also, an integer k belongs to this sequence iff 2k+2 belongs to A073639.

%C The polynomial x^(2k+2) + x + 1 in the definition can be replaced by its reciprocal x^(2k+2) + x^(2k+1) + 1.

%C (2*a(n)+2) is a subsequence of A002475. - _Manfred Scheucher_, Aug 17 2015

%C a(9) >= (A002475(29) - 2)/2 = 5098.

%p select(n -> (Irreduc(x^(2*n+2)+x+1) mod 2) and (Primitive(x^(2*n+2)+x+1) mod 2), [$0..500]); # _Robert Israel_, Aug 17 2015

%o (PARI) polisprimitive(poli)=np = 2^poldegree(poli)-1; if (type((x^np-1)/poli) != "t_POL", return (0)); forstep(k=np-1, 1, -1, if (type((x^k-1)/poli) == "t_POL", return (0));); return(1);

%o lista(nn) = {for (n=0, nn, poli = Mod(1,2)*(x^(2*n+2)+x+1); if (polisirreducible(poli) && polisprimitive(poli), print1(n, ", ")););} \\ _Michel Marcus_, May 27 2013

%o (Sage)

%o def is_primitive(p):

%o d = 2^(p.degree())-1

%o if not p.divides(x^d-1): return False

%o for k in (d//q for q in d.prime_factors()):

%o if p.divides(x^k-1): return False

%o return True

%o P.<x> = GF(2)[]

%o for n in range(1,1000):

%o p = x^(2*n+2)+x+1

%o if p.is_irreducible() and is_primitive(p):

%o print(n)

%o # Modification of the A002475 Script by _Ruperto Corso_

%o # _Manfred Scheucher_, Aug 17 2015

%Y Cf. A002475, A073639, A100730.

%K nonn,more,hard

%O 1,3

%A _Max Alekseyev_, Dec 02 2007, Feb 15 2008

%E a(2)=1 inserted by _Michel Marcus_, May 29 2013