OFFSET
0,2
COMMENTS
A string is (3+)-free if it contains no block of the form xxxa, where a is the first letter of x.
LINKS
G. Badkobeh and M. Crochemore, Infinite binary words containing repetitions of odd period, Info. Proc. Letters 115 (2015) 543-547.
A. Shur, Growth properties of power-free languages, Computer Sci. Rev. 6 (2012), 187-208.
FORMULA
It is known that lim a(n)^(1/n) exists, and is between 1.7951246 and 1.7951264 (Shur, table A.1).
PROG
(Python)
from itertools import product
def f(s): # (3+)-free
for l in range(1, (len(s)-1)//3 + 1):
for i in range(len(s) - 3*l):
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]:
return False
return True
def a(n):
if n == 0: return 1
return 2*sum(1 for w in product("01", repeat=n-1) if f("0"+"".join(w)))
print([a(n) for n in range(16)]) # Michael S. Branicky, Aug 29 2023
(Python) # faster, but > memory, for initial segment of sequence
from itertools import islice
def incf(s): # incrementally (3+)-free
for l in range(1, (len(s)-1)//3 + 1):
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]:
return False
return True
def agen():
yield 1
F = set("0")
while True:
yield 2*len(F)
Fnew = set(c+i for c in F for i in "01" if incf(c+i))
F = Fnew
print(list(islice(agen(), 21))) # Michael S. Branicky, Aug 29 2023
(Python)
from re import compile
def A365253(n):
if n == 0: return 1
r = compile(r'(.)(.*)\1\2\1\2\1')
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Aug 29 2023
EXTENSIONS
a(29)-a(33) from Michael S. Branicky, Aug 29 2023
a(34)-a(35) from Michael S. Branicky, Aug 31 2023
STATUS
approved