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

%I #38 Feb 28 2016 14:05:22

%S 5,17,23,29,43,53,71,79,83,89,101,107,113,127,139,149,151,163,173,179,

%T 181,197,199,223,227,233,251,257,263,269,271,277,281,293,307,311,317,

%U 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

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

%C "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).

%C 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]

%H Antti Karttunen, <a href="/A091209/b091209.txt">Table of n, a(n) for n = 1..71800</a>

%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing this sequence.</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences related to binary encoded polynomials over GF(2)</a>

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

%F Other identities. For all n >= 1:

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

%p Primes:= select(isprime,[2,seq(2*i+1,i=1..1000)]):

%p filter:= proc(n) local L,x;

%p L:= convert(n,base,2);

%p Irreduc(add(L[i]*x^(i-1),i=1..nops(L))) mod 2;

%p end proc:

%p remove(filter,Primes); # _Robert Israel_, May 17 2015

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

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

%Y Intersection of A000040 and A091242.

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

%Y Left inverse: A235043.

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

%Y Cf. also A235041-A235042, A234742.

%K nonn

%O 1,1

%A _Antti Karttunen_, Jan 03 2004