cp's OEIS Frontend

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

%I A342510 #24 Mar 18 2021 19:12:02
%S A342510 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,
%T A342510 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,
%U A342510 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,2
%N A342510 a(n) = k where Z_k is the largest Zimin word that n (read as a binary word) does not avoid.
%C A342510 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.
%C A342510 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.
%C A342510 a(n) >= 2 for all n >= 2^4.
%C A342510 a(n) >= 3 for all n >= 2^28.
%C A342510 For any fixed k, a(n) >= k for sufficiently large n, however there exists a value of a(n) = 3 with n >= 2^10482.
%C A342510 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.
%H A342510 Peter Kagey, <a href="/A342510/b342510.txt">Table of n, a(n) for n = 0..8191</a>
%H A342510 Peter Kagey, <a href="https://codegolf.stackexchange.com/q/220679/53884">Matching ABACABA-type patterns</a>, Code Golf Stack Exchange.
%H A342510 Danny Rorabaugh, <a href="http://arxiv.org/abs/1509.04372">Toward the Combinatorial Limit Theory of Free Words</a>, arXiv preprint arXiv:1509.04372 [math.CO], 2015.
%H A342510 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sesquipower">Sesquipower</a>.
%e A342510 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".
%e A342510 No substring is an instance of the Zimin word Z_4 = ABACABADABACABA, so a(10101939)= 3.
%o A342510 (Python)
%o A342510 def sd(w): # sesquipower degree
%o A342510   return 1 + max([0]+[sd(w[:i]) for i in range(1, (len(w)+1)//2) if w[:i] == w[-i:]])
%o A342510 def a(n):
%o A342510   w = bin(n)[2:]
%o A342510   return max(sd(w[i:j]) for i in range(len(w)) for j in range(i+1, len(w)+1))
%o A342510 print([a(n) for n in range(87)]) # _Michael S. Branicky_, Mar 15 2021
%Y A342510 Cf. A001045.
%Y A342510 Cf. A342511, A342512.
%K A342510 nonn,base
%O A342510 0,6
%A A342510 _Peter Kagey_, Mar 14 2021