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
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Jan 16 2013
EXTENSIONS
a(23)-a(32) from Michael S. Branicky, Mar 21 2022
STATUS
approved