login
Primes whose binary representation encodes a polynomial irreducible over GF(2).
26

%I #33 Feb 06 2023 10:02:16

%S 2,3,7,11,13,19,31,37,41,47,59,61,67,73,97,103,109,131,137,157,167,

%T 191,193,211,229,239,241,283,313,379,397,419,433,463,487,499,557,563,

%U 587,601,607,613,617,631,647,661,677,701,719,757,761,769,787,827,859

%N Primes whose binary representation encodes a polynomial irreducible 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 Subsequence with Hamming weight nonprime starts 2, 1019, 1279, 1531, 1663, 1759, 1783, 1789, 2011, 2027, 2543, 2551, ... [_Joerg Arndt_, Nov 01 2013]. These are now given by A255569. - _Antti Karttunen_, May 14 2015

%H Antti Karttunen, <a href="/A091206/b091206.txt">Table of n, a(n) for n = 1..10226; all terms up to 1048357, binary length 20</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(A091207(n)) = A014580(A091208(n)).

%t okQ[p_] := Module[{id, pol, x}, id = IntegerDigits[p, 2] // Reverse; pol = id.x^Range[0, Length[id] - 1]; IrreduciblePolynomialQ[pol, Modulus -> 2]];

%t Select[Prime[Range[1000]], okQ] (* _Jean-François Alcover_, Feb 06 2023 *)

%o (PARI)

%o is(n)=polisirreducible( Mod(1,2) * Pol(digits(n,2)) );

%o forprime(n=2,10^3,if (is(n), print1(n,", ")));

%o \\ _Joerg Arndt_, Nov 01 2013

%Y Intersection of A014580 and A000040.

%Y Apart from a(2) = 3 a subsequence of A027697. The numbers in A027697 but not here are listed in A238186.

%Y Also subsequence of A235045 (its primes. Cf. also A235041-A235042).

%Y Cf. A091209 (Primes whose binary expansion encodes a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)), A257688 (either 1, prime or irreducible over GF(2)).

%Y Subsequence: A255569.

%K nonn

%O 1,1

%A _Antti Karttunen_, Jan 03 2004