A091209 Primes whose binary representation encodes a polynomial reducible over GF(2).

5, 17, 23, 29, 43, 53, 71, 79, 83, 89, 101, 107, 113, 127, 139, 149, 151, 163, 173, 179, 181, 197, 199, 223, 227, 233, 251, 257, 263, 269, 271, 277, 281, 293, 307, 311, 317, 331, 337, 347, 349, 353, 359, 367, 373, 383, 389, 401, 409, 421, 431, 439, 443, 449, 457, 461, 467, 479, 491, 503, 509, 521, 523

Offset

1,1

Comments

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).

Except for 3, all primes with even Hamming weight (A027699) are terms, see A238186 for the subsequence of primes with odd Hamming weight. [Joerg Arndt and Antti Karttunen, Feb 19 2014]

Links

Antti Karttunen, Table of n, a(n) for n = 1..71800

A. Karttunen, Scheme-program for computing this sequence.

Index entries for sequences related to binary encoded polynomials over GF(2)

Formula

a(n) = A000040(A091210(n)) = A091242(A091211(n)).

Other identities. For all n >= 1:

A235043(a(n)) = n. [A235043 works as a left inverse of this sequence.]

Maple

Primes:= select(isprime, [2, seq(2*i+1, i=1..1000)]):
filter:= proc(n) local L, x;
    L:= convert(n, base, 2);
    Irreduc(add(L[i]*x^(i-1), i=1..nops(L))) mod 2;
end proc:
remove(filter, Primes); # Robert Israel, May 17 2015

Mathematica

Select[Prime[Range[2, 100]], !IrreduciblePolynomialQ[bb = IntegerDigits[#, 2]; Sum[bb[[k]] x^(k-1), {k, 1, Length[bb]}], Modulus -> 2]&] (* Jean-François Alcover, Feb 28 2016 *)

Prog

(PARI) forprime(p=2, 10^3, if( ! polisirreducible( Mod(1, 2)*Pol(binary(p)) ), print1(p, ", ") ) ); \\ Joerg Arndt, Feb 19 2014

Crossrefs

Intersection of A000040 and A091242.

Disjoint union of A238186 and (A027699 \ {3}).

Left inverse: A235043.

Cf. A091206 (Primes whose binary expansion encodes a polynomial irreducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)).

Cf. also A235041-A235042, A234742.

Sequence in context: A322985 A240031 A260427 * A307471 A226671 A226674

Adjacent sequences: A091206 A091207 A091208 * A091210 A091211 A091212

Keyword

nonn

Author

Antti Karttunen, Jan 03 2004

Status

approved