A339187 a(n) is the maximum of f(s) for all binary sequences s of length n where f(s) denote the duplication distance between s and its root.

0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15

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

Table of n, a(n) for n=1..32.

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

Sequence in context: A335380 A077773 A308754 * A309430 A076370 A112318

Adjacent sequences: A339184 A339185 A339186 * A339188 A339189 A339190

Keyword

nonn,more

Author

Michel Marcus, Nov 27 2020

Status

approved