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,2

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].

Links

Table of n, a(n) for n=0..38.

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

Formula

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

Example

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.

Crossrefs

Cf. A001037, A169913, A169914.

Sequence in context: A094341 A255939 A333177 * A316994 A316993 A092944

Adjacent sequences: A169909 A169910 A169911 * A169913 A169914 A169915

Keyword

nonn,nice

Author

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

Extensions

More terms from David Applegate, Jul 19 2010

Status

approved