A162570 -id:A162570 - cp's OEIS frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

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

A268274 Numbers n such that x^n * (x+1)^(n-1) + 1 is irreducible over GF(2).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 21, 32, 33, 36, 53, 64, 85, 89, 148, 312, 404, 3080, 8380, 11684, 16384, 18089, 21096, 53492, 78484, 192248

Offset: 1

Joerg Arndt, Mar 02 2016

Any subsequent terms are > 2 * 10^5. - Lucas A. Brown, Dec 01 2022

Cf. A162570 (corresponding to powers of 2 in this sequence).

isok(n) = polisirreducible(Mod(1, 2)*x^n * (x+1)^(n-1) + 1); \\ Michel Marcus, Mar 03 2016

P. = GF(2)[]
for n in range(1, 10^5):
       if (x^n * (x+1)^(n-1) + 1).is_irreducible():
           print(n)

a(26) from Lucas A. Brown, Dec 01 2022

A335383 a(n) is the number of irreducible Mersenne polynomials in GF(2)[x] that have degree n.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 0, 4, 2, 2, 2, 0, 2, 6, 0, 6, 2, 0, 2, 2, 2, 4, 0, 4, 0, 0, 8, 2, 2, 8, 0, 4, 2, 2, 2, 0, 0, 6, 0, 4, 0, 0, 2, 0, 2, 8, 0, 8, 0, 0, 8, 0, 0, 4, 0, 8, 2, 0, 8, 0, 2, 8, 0, 4, 0, 0, 4, 0, 0, 10, 0, 6, 2, 0, 2, 0, 0, 4, 0, 6, 0, 0, 6, 0, 2, 2, 0, 2, 0, 0, 2, 2, 2, 4, 0, 8, 4, 0, 6

Offset: 2

Luis H. Gallardo, Jun 04 2020

nonn

A Mersenne polynomial is a binary (i.e., an element of GF(2)[x]) polynomial M, of degree > 1, such that M+1 has only 0 and 1 as roots in a fixed algebraic closure of GF(2).
If for some positive integers  a,b, M = x^a(x+1)^b+1 is an irreducible Mersenne polynomial, then gcd(a,b)=1. This condition is not sufficient.
There is no known formula for a(n). Of course it is bounded above by the total number of prime (irreducible) binary polynomials of degree n, but this is a too weak upper bound. A trivial, better upper bound, is simply n-1, the total number of Mersenne polynomials (prime or not) of degree n.

			For n = 5 one has a(5) = 2 since there are 2 irreducible Mersenne polynomials of degree 5. Namely, x^2*(x+1)^3+1 and x^3*(x+1)^2+1.
For n = 8, a(8) = 0 since there are no irreducible Mersenne polynomial of degree 8.

L. H. Gallardo and O. Rahavandrainy, On even (unitary) perfect polynomials over F_2, Finite Fields Appl. 18, no. 5, (2012), 920-932.
L. H. Gallardo and O. Rahavandrainy, Characterization of Sporadic perfect polynomials over F_2, Funct. Approx. Comment. Math.,(2016), 7-21.
L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over F_2, Finite Fields Appl. 59 (2019), 284-296.
L. H. Gallardo and O. Rahavandrainy, On (unitary) perfect polynomials over F_2 with only Mersenne primes as odd divisors, arXiv:1908.00106 [math.NT], 2019.

Cf. A267918, A272486, A162570.

a(n) = sum(k=1, n-1, polisirreducible(Mod(1, 2)*(x^(n-k)*(x+1)^k+1))); \\ Michel Marcus, Jun 07 2020

a(A272486(n)) = 0. - Michel Marcus, Jun 07 2020

cp's OEIS Frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A268274 Numbers n such that x^n * (x+1)^(n-1) + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Sage

Extensions

A335383 a(n) is the number of irreducible Mersenne polynomials in GF(2)[x] that have degree n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula