A209284 Number of "semiperiodic" binary words of length n.

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

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

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

Adjacent sequences: A209281 A209282 A209283 * A209285 A209286 A209287

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 16 2013

Extensions

a(23)-a(32) from Michael S. Branicky, Mar 21 2022

Status

approved