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,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.

Sequence in context: A043557 A055027 A214574 * A298071 A246920 A244964

Adjacent sequences: A342507 A342508 A342509 * A342511 A342512 A342513

Keyword

nonn,base

Author

Peter Kagey, Mar 14 2021

Status

approved