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

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

Offset: 1

Author

Max Alekseyev, Dec 02 2007, Feb 15 2008

Keywords

• nonn
• more
• hard

Comments

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

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

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

(2*a(n)+2) is a subsequence of A002475. - Manfred Scheucher, Aug 17 2015

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

Crossrefs

Cf. A002475, A073639, A100730.

Programs

Maple

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

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

Sage

def is_primitive(p):
    d = 2^(p.degree())-1
    if not p.divides(x^d-1): return False
    for k in (d//q for q in d.prime_factors()):
        if p.divides(x^k-1): return False
    return True
P. = GF(2)[]
for n in range(1,1000):
    p = x^(2*n+2)+x+1
    if p.is_irreducible() and is_primitive(p):
        print(n)
# Modification of the A002475 Script by Ruperto Corso
# Manfred Scheucher, Aug 17 2015

Extensions

a(2)=1 inserted by Michel Marcus, May 29 2013