OFFSET
1,3
COMMENTS
The duplication distance between two sequences is the minimum number of duplications required to convert the shorter sequence to the longer one.
So for each binary sequence s of length n, we are looking for the number duplication operations of the form x = abc --> y = abbc, where x and y are sequences and a, b, and c are their substrings, needed to generate s starting from a squarefree sequence from the set {0, 1, 01, 10, 010, 101}.
Then a(n) will be the maximum of the duplication distance over all binary sequences.
LINKS
Noga Alon, Jehoshua Bruck, Farzad Farnoud, and Siddharth Jain, Duplication Distance to the Root for Binary Sequences, arXiv:1611.05537 [cs.IT], 2016.
Jarosław Grytczuk and Szymon Stankiewicz, Square-free reducts of words, arXiv:2011.12822 [math.CO], 2020.
PROG
(Python)
from itertools import product
from functools import lru_cache
@lru_cache(maxsize=None)
def f(s):
if s in {"0", "1", "01", "10", "010", "101"}: return 0
# min over 1+f(abc) for each b where s=abbc; |b|=h, b starts at index i
return min(1+f(s[:i]+s[i+h:]) for i in range(len(s))
for h in range(1, (len(s)-i+1)//2+1) if s[i:i+h]==s[i+h:i+2*h])
def a(n): # by symmetry, it is enough to check strings starting with "0"
return max(f("0"+"".join(s)) for s in product("01", repeat=n-1))
print([a(n) for n in range(1, 15)]) # Michael S. Branicky, Nov 27 2020
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Michel Marcus, Nov 27 2020
STATUS
approved