A091242 Reducible polynomials over GF(2), coded in binary.

4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 88

Offset: 1

Author

Antti Karttunen, Jan 03 2004

Keywords

• nonn

Comments

"Coded in binary" 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 a(k)=0 or 1). - M. F. Hasler, Aug 18 2014

The reducible polynomials in GF(2)[X] are the analog to the composite numbers A002808 in the integers.

It follows that the sequence is closed under application of A048720(.,.), which effects multiplication of the coded polynomials. It is also closed under application of blue code, A193231. The majority of the terms are coded multiples of X^1 (represented by 2) and/or X^1+1 (represented by 3): see A005843 and A001969 respectively. A246157 lists the other terms. - Peter Munn, Apr 20 2021

Examples

			For example, 5 = 101 in binary encodes the polynomial x^2+1 which is factored as (x+1)^2 in the polynomial ring GF(2)[X].
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Antti Karttunen, Scheme-program for computing this sequence.
• Index entries for sequences operating on GF(2)[X]-polynomials

Crossrefs

Inverse: A091246. Almost complement of A014580. Union of A091209 & A091212. First differences: A091243. Characteristic function: A091247. In binary format: A091254.

Number of degree-n reducible polynomials: A058766.

Subsequences: A001969\{0,3}, A005843\{0,2}, A246156, A246157, A246158, A316970.

Cf. A002808, A048720, A193231.

Programs

Maple

filter:= proc(n) local L;
  L:= convert(n,base,2);
  not Irreduc(add(L[i]*x^(i-1),i=1..nops(L))) mod 2
end proc:
select(filter, [$2..200]); # Robert Israel, Aug 30 2018

Mathematica

okQ[n_] := Module[{x, id = IntegerDigits[n, 2] // Reverse}, !IrreduciblePolynomialQ[id.x^Range[0, Length[id]-1], Modulus -> 2]];
Select[Range[2, 200], okQ] (* Jean-François Alcover, Jan 04 2022 *)

Extensions

Edited by M. F. Hasler, Aug 18 2014