A169912 Number of irreducible Boolean polynomials of degree n.

1, 2, 1, 3, 5, 9, 19, 39, 77, 168, 323, 682, 1424, 2902, 5956, 12368, 25329, 51866, 106427, 217216, 442313, 902921, 1833029, 3719745, 7548521, 15264350, 30859444, 62355854, 125773168, 253461052, 510471015, 1027067090, 2065390101, 4151081457, 8336751732, 16734781946, 33583213577, 67357328359, 135056786787

Offset: 0

Author

David Applegate, Marc LeBrun and N. J. A. Sloane, Jul 11 2010

Keywords

• nonn
• nice

Comments

Let B be the Boolean ring {0,1} with 0+0=0, 0+1=1+1=1, 0*0=0*1=0, 1*1=1 (0 = FALSE, 1 = TRUE, + = OR, * = AND); then a(n) = number of irreducible elements of degree n in the polynomial ring B[X].

Examples

			a(0) = 1: 1.
a(1) = 2: X and X+1.
a(2) = 1: X^2+1 (note that X^2+X+1 = (X+1)^2 is reducible).
a(3) = 3: X^3+1, X^3+X+1, X^3+X^2+1.
		

Links

• Benjamin Baily, Justine Dell, Henry L. Fleischmann, Faye Jackson, Steven J. Miller, Ethan Pesikoff, and Luke Reifenberg, Irreducibility over the Max-Min Semiring, arXiv:2111.09786 [math.CO], 2021.
• Index entries for sequences related to carryless arithmetic

Crossrefs

Cf. A001037, A169913, A169914.

Formula

a(n) + A169913(n) = 2^n.

Extensions

More terms from David Applegate, Jul 19 2010