login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A342510 a(n) = k where Z_k is the largest Zimin word that n (read as a binary word) does not avoid. 3
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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 19:45 EDT 2022. Contains 353957 sequences. (Running on oeis4.)