A074710 -id:A074710 - cp's OEIS frontend

A057460 Numbers k such that x^k + x^2 + 1 is irreducible over GF(2).

1, 3, 5, 11, 21, 29, 35, 93, 123, 333, 845, 4125, 10437, 10469, 14211, 20307, 34115, 47283, 50621, 57341, 70331, 80141

Offset: 1

Robert G. Wilson v, Sep 27 2000

Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

Joerg Arndt, Matters Computational (The Fxtbook)
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, Springer-Verlag, Berlin, 1994, 1-23, See Table 2.
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.
H. Fredricksen, R. Wisniewski, On trinomials x^n + x^2 + 1 and x^{8l+-1} + x^k + 1 irreducible overGF(2), Inform. and Control 50 (1981), no. 1, 58--63. MR0665139 (84i:12013). Gives first 20 terms.
Index entries for sequences related to trinomials over GF(2)

isok(n) = polisirreducible(Mod(1,2)*(x^n + x^2 + 1)); \\ Michel Marcus, Aug 23 2015

Confirmed by Richard P. Brent, Sep 05 2002

a(21) and a(22) from Lucas A. Brown, Nov 28 2022

A335379 a(n) is the number of Mersenne prime (irreducible) polynomials M = x^k(x+1)^(n-k)+1 of degree n in GF(2)[x] (k goes from 1 to n-1) such that Phi_7(M) has an odd number of prime divisors (omega(Phi_7(M)) is odd).

Original entry on oeis.org

1, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2

Offset: 2

Luis H. Gallardo, Jun 03 2020

nonn

Phi_7(x)=1+x+x^2+x^3+x^4+x^5+x^6, is the 7th cyclotomic polynomial; omega(P(x)) counts the 2 X 2 distinct irreducible divisors of the binary polynomial P(x) in GF(2)[x].

It is surprising that a(n) be so small (conjecturally it is always 1 or 2). The sequence appeared when working the special case p=7 of a conjecture (see Links) about prime divisors in GF(2)[x] of the composed cyclotomic polynomial Phi_p(M), where p is a prime number and M is a Mersenne irreducible polynomial.

			For n=4 a(4)= 0 (the sequence begins a(2)=1,a(3)=2,...), since there is no Mersenne polynomial M of degree 4 in GF(2)[x] such that omega(Phi_7(M)) is odd.

Antti Karttunen, Table of n, a(n) for n = 2..1700
L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over GF(2), Finite Fields Appl. 59 (2019), 284-296.

Cf. A057460 (A074710), A071642, A267918, A272486, A162570.

a(n)={my(phi7=polcyclo(7)); sum(k=1, n-1, my(p=Mod(x^k * (x+1)^(n-k) + 1, 2)); polisirreducible(p) && #(factor(subst(phi7, x, p))~)%2)} \\ Andrew Howroyd, Jun 04 2020

Terms a(22) and beyond from Andrew Howroyd, Jun 04 2020

cp's OEIS Frontend

A057460 Numbers k such that x^k + x^2 + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions