login
Composite numbers whose binary representation encodes a polynomial reducible over GF(2).
13

%I #35 May 18 2015 10:33:47

%S 4,6,8,9,10,12,14,15,16,18,20,21,22,24,26,27,28,30,32,33,34,35,36,38,

%T 39,40,42,44,45,46,48,49,50,51,52,54,56,57,58,60,62,63,64,65,66,68,69,

%U 70,72,74,75,76,77,78,80,81,82,84,85,86,88,90,92,93,94,95,96,98,99

%N Composite numbers 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 From _Reinhard Zumkeller_, Jul 05-12 2011, values for maximum n corrected by _Antti Karttunen_, May 18 2015: (Start)

%C a(n) = A192506(n) for n <= 36.

%C a(n) = A175526(n) for n <= 36.

%C (End)

%H Antti Karttunen, <a href="/A091212/b091212.txt">Table of n, a(n) for n = 1..55429</a>

%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Scheme-program for computing beginning of 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) = A091242(A091213(n)).

%o (PARI)

%o isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from _Charles R Greathouse IV_

%o isA091212(n) = ((n > 1) && !isprime(n) && !isA014580(n));

%o n = 0; i = 0; while(n < 2^16, n++; if(isA091212(n), i++; write("b091212.txt", i, " ", n)));

%Y Intersection of A002808 and A091242.

%Y Cf. A257688 (complement, either 1, irreducible in GF(2)[X] or prime), A091206 (prime and irreducible), A091209 (prime and reducible), A091214 (nonprime and irreducible).

%Y Cf. A091213, A236861, A235036 (a subsequence, apart from 1).

%Y Differs from both A175526 and A192506 for the first time at n=37, where a(37) = 56, while A175526(37) = A192506(37) = 55, a term missing from here (as 55 encodes a polynomial which is irreducible in GF(2)[X]).

%Y Differs from its subsequence A205783(n+1) for the first time at n=47, where a(47) = 69, while 69 is missing from A205783.

%K nonn

%O 1,1

%A _Antti Karttunen_, Jan 03 2004