A209284 - OEIS

%I #33 Mar 21 2022 11:10:31

%S 2,2,4,4,10,14,22,32,70,122,178,286,518,898,1610,2666,4702,8506,14982,

%T 26668,48022,85904,155102,282096,514510,944036,1734736,3194838,

%U 5898576,10945970,20322550,37823268

%N Number of "semiperiodic" binary words of length n.

%C 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.

%C Alternatively, a word w is semiperiodic if the length of its shortest period is <= |w| - R(w).

%H A. Carpi and A. de Luca, <a href="https://doi.org/10.1016/S0304-3975(01)00218-3">Semiperiodic words and root-conjugacy</a>, Theor. Comput. Sci. 292 (2003), 111-130.

%e For n = 5 there are 10 semiperiodic words:  00000, 00100, 01001, 01010, 01101, and their complements.

%o (Python)

%o from itertools import product

%o def R(w):

%o     for l in range(len(w)):

%o         found = False

%o         for i in range(len(w)-l):

%o             f = w[i:i+l]

%o             if f+"0" in w and f+"1" in w: found = True; break

%o             if found: break

%o         if not found: return l

%o def H(w):

%o     for l in range(1, len(w)):

%o         prefix = w[:l]

%o         if "0"+prefix not in w and "1"+prefix not in w: return l

%o     return len(w)

%o def S(w): return R(w) < H(w)

%o def a(n):

%o     return 2*sum(1 for w in product("01", repeat=n-1) if S("0"+"".join(w)))

%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Mar 21 2022

%K nonn,more

%O 1,1

%A _Jeffrey Shallit_, Jan 16 2013

%E a(23)-a(32) from _Michael S. Branicky_, Mar 21 2022