Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #21 Aug 31 2023 12:01:42
%S 1,2,4,8,14,26,48,86,156,282,506,910,1638,2936,5276,9482,17012,30542,
%T 54838,98440,176726,317268,569516,1022368,1835320,3294596,5914262,
%U 10616932,19058674,34212776,61416376,110250050,197912878,355278872,637770308,1144878550
%N Number of (3+)-free binary strings of length n.
%C A string is (3+)-free if it contains no block of the form xxxa, where a is the first letter of x.
%H G. Badkobeh and M. Crochemore, <a href="http://dx.doi.org/10.1016/j.ipl.2015.01.004">Infinite binary words containing repetitions of odd period</a>, Info. Proc. Letters 115 (2015) 543-547.
%H A. Shur, <a href="https://doi.org/10.1016/j.cosrev.2012.09.001">Growth properties of power-free languages</a>, Computer Sci. Rev. 6 (2012), 187-208.
%F It is known that lim a(n)^(1/n) exists, and is between 1.7951246 and 1.7951264 (Shur, table A.1).
%o (Python)
%o from itertools import product
%o def f(s): # (3+)-free
%o for l in range(1, (len(s)-1)//3 + 1):
%o for i in range(len(s) - 3*l):
%o if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l] and s[i]==s[i+3*l]:
%o return False
%o return True
%o def a(n):
%o if n == 0: return 1
%o return 2*sum(1 for w in product("01", repeat=n-1) if f("0"+"".join(w)))
%o print([a(n) for n in range(16)]) # _Michael S. Branicky_, Aug 29 2023
%o (Python) # faster, but > memory, for initial segment of sequence
%o from itertools import islice
%o def incf(s): # incrementally (3+)-free
%o for l in range(1, (len(s)-1)//3 + 1):
%o if s[-3*l-1:-2*l-1]==s[-2*l-1:-l-1]==s[-l-1:-1] and s[-3*l-1]==s[-1]:
%o return False
%o return True
%o def agen():
%o yield 1
%o F = set("0")
%o while True:
%o yield 2*len(F)
%o Fnew = set(c+i for c in F for i in "01" if incf(c+i))
%o F = Fnew
%o print(list(islice(agen(),21))) # _Michael S. Branicky_, Aug 29 2023
%o (Python)
%o from re import compile
%o def A365253(n):
%o if n == 0: return 1
%o r = compile(r'(.)(.*)\1\2\1\2\1')
%o return 2*sum(not r.search(format(k,f'0{n}b')) for k in range(2**(n-1))) # _Pontus von Brömssen_, Aug 29 2023
%Y Cf. A028445.
%K nonn
%O 0,2
%A _Jeffrey Shallit_, Aug 29 2023
%E a(29)-a(33) from _Michael S. Branicky_, Aug 29 2023
%E a(34)-a(35) from _Michael S. Branicky_, Aug 31 2023