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

Comments

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

Links

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

Example

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

Mathematica

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

Prog

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

Crossrefs

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.

Sequence in context: A321657 A040116 A155153 * A197227 A091206 A357713

Adjacent sequences: A014577 A014578 A014579 * A014581 A014582 A014583

Keyword

nonn

Author

David Petry (petry(AT)accessone.com)

Status

approved