A169914 -id:A169914 - cp's OEIS frontend

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

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

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

			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.

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

Cf. A001037, A169913, A169914.

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

More terms from David Applegate, Jul 19 2010

A169913 Number of reducible Boolean polynomials of degree n.

Original entry on oeis.org

0, 0, 3, 5, 11, 23, 45, 89, 179, 344, 701, 1366, 2672, 5290, 10428, 20400, 40207, 79206, 155717, 307072, 606263, 1194231, 2361275, 4668863, 9228695, 18290082, 36249420, 71861874, 142662288, 283409860, 563270809, 1120416558, 2229577195, 4438853135, 8843117452, 17624956422, 35136263159, 70081625113, 139821120157

Offset: 0

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

nonn

See A169912 for details.

Index entries for sequences related to carryless arithmetic

Cf. A169912, A169914.

More terms from David Applegate, Jul 19 2010

cp's OEIS Frontend

A169912 Number of irreducible Boolean polynomials of degree n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions