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,3

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.

Links

Table of n, a(n) for n=1..8.

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

Prog

(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.<x> = 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

Crossrefs

Cf. A002475, A073639, A100730.

Sequence in context: A190186 A032250 A215790 * A215954 A098425 A098408

Adjacent sequences: A133482 A133483 A133484 * A133486 A133487 A133488

Keyword

nonn,more,hard

Author

Max Alekseyev, Dec 02 2007, Feb 15 2008

Extensions

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

Status

approved