login
A209284
Number of "semiperiodic" binary words of length n.
0
2, 2, 4, 4, 10, 14, 22, 32, 70, 122, 178, 286, 518, 898, 1610, 2666, 4702, 8506, 14982, 26668, 48022, 85904, 155102, 282096, 514510, 944036, 1734736, 3194838, 5898576, 10945970, 20322550, 37823268
OFFSET
1,1
COMMENTS
A word w is "semiperiodic" if R(w) < H(w), where R(w) is the smallest natural number such that there is no right special factor of length n. A factor is a contiguous block occurring within w. A factor f is right special if fa and fb both appear in w for some a not equal to b. H(w) is the length of the shortest prefix of w which appears only once in w.
Alternatively, a word w is semiperiodic if the length of its shortest period is <= |w| - R(w).
LINKS
A. Carpi and A. de Luca, Semiperiodic words and root-conjugacy, Theor. Comput. Sci. 292 (2003), 111-130.
EXAMPLE
For n = 5 there are 10 semiperiodic words: 00000, 00100, 01001, 01010, 01101, and their complements.
PROG
(Python)
from itertools import product
def R(w):
for l in range(len(w)):
found = False
for i in range(len(w)-l):
f = w[i:i+l]
if f+"0" in w and f+"1" in w: found = True; break
if found: break
if not found: return l
def H(w):
for l in range(1, len(w)):
prefix = w[:l]
if "0"+prefix not in w and "1"+prefix not in w: return l
return len(w)
def S(w): return R(w) < H(w)
def a(n):
return 2*sum(1 for w in product("01", repeat=n-1) if S("0"+"".join(w)))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Mar 21 2022
CROSSREFS
Sequence in context: A320434 A329394 A057784 * A321468 A288044 A081164
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Jan 16 2013
EXTENSIONS
a(23)-a(32) from Michael S. Branicky, Mar 21 2022
STATUS
approved