A342510 - OEIS

A342510

a(n) = k where Z_k is the largest Zimin word that n (read as a binary word) does not avoid.

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

Zimin words are defined recursively: Z_1 = A, Z_2 = ABA, Z_3 = ABACABA, and Z_{i+1} = Z_i a_{i+1} Z_i.

Every Zimin word Z_i is an "unavoidable" word, meaning that every sufficiently long string over a finite alphabet contains a substring that is an instance of Z_i. A word w is instance of a Zimin word Z_i if there's a nonerasing monoid homomorphism from Z_i to w.

a(n) >= 2 for all n >= 2^4.

a(n) >= 3 for all n >= 2^28.

For any fixed k, a(n) >= k for sufficiently large n, however there exists a value of a(n) = 3 with n >= 2^10482.

The first occurrence of k is when n = A001045(2^k), that is, the binary expansion of n is "1010101...01" with 2^k - 1 bits.

LINKS

Peter Kagey, Table of n, a(n) for n = 0..8191

Peter Kagey, Matching ABACABA-type patterns, Code Golf Stack Exchange.

Danny Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372 [math.CO], 2015.

Wikipedia, Sesquipower.

EXAMPLE

For n = 10101939, the binary representation is "100110100010010010110011", and the substring "0010010010" is an instance of the Zimin word Z_3 = ABACABA with A = "0", B = "01", and C = "01".

No substring is an instance of the Zimin word Z_4 = ABACABADABACABA, so a(10101939)= 3.

PROG

(Python)

def sd(w): # sesquipower degree

return 1 + max([0]+[sd(w[:i]) for i in range(1, (len(w)+1)//2) if w[:i] == w[-i:]])

def a(n):

w = bin(n)[2:]

return max(sd(w[i:j]) for i in range(len(w)) for j in range(i+1, len(w)+1))

print([a(n) for n in range(87)]) # Michael S. Branicky, Mar 15 2021

CROSSREFS

Cf. A001045.

Cf. A342511, A342512.