|
| |
|
|
A327544
|
|
Number of length-n binary words whose longest repeated suffix equals the longest repeated prefix.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
