login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of (3+)-free binary strings of length n.
1

%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