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

Offset: 0

Author

Peter Kagey, Mar 14 2021

Keywords

• nonn
• base

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.

Examples

			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.
		

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.

Crossrefs

Cf. A001045.

Cf. A342511, A342512.

Programs

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