A327544 Number of length-n binary words whose longest repeated suffix equals the longest repeated prefix.

2, 4, 4, 10, 16, 28, 44, 90, 156, 270, 488, 886, 1620, 2986, 5460, 10120, 18890, 35284, 66290, 124964, 236040, 447460, 850492, 1620016, 3092652, 5915898, 11336182, 21760238, 41836338, 80549326, 155296862, 299788294, 579396418, 1121031734, 2171251698

Offset

1,1

Comments

The longest repeated suffix of a word x is the longest suffix (possibly empty) that occurs at least twice as a contiguous block inside x, and analogously for the prefix.

Links

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

Michael S. Branicky, Python program.

Example

For n = 5 these binary words are 00000, 00100, 00110, 01001, 01010, 01100, 01101, 01110 and their reversals.

Prog

(Python) # see link for faster version
from itertools import product
def lrp(s): # longest repeated prefix (overlaps allowed)
  for i in range(len(s)-1, 0, -1):
    if s.find(s[:i], 1) >= 0: return s[:i]
  return ""
def a(n):
  if n == 1: return 2
  c = 0
  for p in product("01", repeat=n-1):
    b = "1" + "".join(p)
    if lrp(b) == lrp(b[::-1])[::-1]: c += 1
  return 2*c
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Feb 05 2021

Crossrefs

Sequence in context: A267311 A118336 A193852 * A202076 A199825 A121049

Adjacent sequences: A327541 A327542 A327543 * A327545 A327546 A327547

Keyword

nonn

Author

Jeffrey Shallit, Sep 16 2019

Extensions

a(29) and beyond from Michael S. Branicky, Feb 05 2021

Status

approved