A308528 Number of length-n binary words having no nontrivial prefix that is a palindrome of odd length.

2, 4, 4, 8, 12, 24, 40, 80, 148, 296, 568, 1136, 2232, 4464, 8848, 17696, 35244, 70488, 140680, 281360, 562152, 1124304, 2247472, 4494944, 8987656, 17975312, 35946160, 71892320, 143775792, 287551584, 575085472, 1150170944, 2300306644, 4600613288, 9201156088

Offset: 1

Author

Jeffrey Shallit, Jun 06 2019

Keywords

• nonn

Comments

A nontrivial palindrome is one that is of length at least 2.

For n even we have a(n) = 2a(n-1), and for n odd, a(n) = A003000(n).

Examples

			For n = 5, the only words counted are 00101, 00110, 00111, 01100, 01101, 01111 and their binary complements.
		

Links

• Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.

Crossrefs

Cf. A003000, A308529.