login
Binary numbers that represent irreducible polynomials over the rationals with coefficients restricted to {0,1}.
14

%I #16 Mar 30 2012 18:58:12

%S 10,11,101,111,1011,1101,10001,10011,10111,11001,11101,11111,100101,

%T 101001,101011,101111,110101,110111,111011,111101,1000011,1000101,

%U 1000111,1001001,1001101,1001111,1010001,1010011,1010111,1011001

%N Binary numbers that represent irreducible polynomials over the rationals with coefficients restricted to {0,1}.

%C The polynomial x^d(0) + x^d(1) + ... + d(n), where d(i) is 0 or 1 for 0<=i<=n and d(0)=1, matches the binary number d(0)d(1)...d(n). (This is an enumeration of all the nonzero polynomials with coefficients in {0,1}, not just those that are irreducible.)

%e The matching of binary numbers to the first six polynomials irreducible over the field of rational numbers:

%e 10 .... x

%e 11 .... x + 1

%e 101 ... x^2 + 1

%e 111 ... x^2 + x + 1

%e 1011 .. x^3 + x + 1

%t t = Table[IntegerDigits[n, 2], {n, 1, 850}];

%t b[n_] := Reverse[Table[x^k, {k, 0, n}]]

%t p[n_, x_] := t[[n]].b[-1 + Length[t[[n]]]]

%t Table[p[n, x], {n, 1, 15}]

%t u = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],

%t AppendTo[u, n]], {n, 300}];

%t u (* A206074 *)

%t Complement[Range[200], u] (* A205783 *)

%t b[n_] := FromDigits[IntegerDigits[u, 2][[n]]]

%t Table[b[n], {n, 1, 40}] (* A206073 *)

%Y Cf. A171000 (irreducible Boolean polynomials).

%Y Cf. A205783 (complement), A206074 (base 10).

%K nonn,base

%O 1,1

%A _Clark Kimberling_, Feb 03 2012