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

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

Links

Table of n, a(n) for n=1..35.

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

Example

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

Crossrefs

Cf. A003000, A308529.

Sequence in context: A131771 A335974 A047073 * A069753 A181245 A216950

Adjacent sequences: A308525 A308526 A308527 * A308529 A308530 A308531

Keyword

nonn

Author

Jeffrey Shallit, Jun 06 2019

Status

approved