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

Author

Antti Karttunen, Jan 03 2004

Keywords

• nonn

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)

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.

Programs

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

PARI

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

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