A329422 Maximum length of a binary n-similar word.

3, 9, 17, 25, 33, 41, 49, 57, 65, 75

Offset

0,1

Comments

A word w is n-similar if every consecutive pair of identical-length contiguous blocks within w agrees on at most n positions.

References

A. Baranwal, T. Clokie, et al., Similarity of words, in preparation, November 2019.

Links

Table of n, a(n) for n=0..9.

Formula

It is known that a(n) >= 8n+1 and a(n) <= 10n+5 for all n >= 0.

Example

Here are the lexicographically least longest words for n = 0, 1, ..., 9:
0: 010
1: 000111000
2: 00000101111100000
3: 0000000101011111110000000
4: 000000000101010111111111000000000
5: 00000000000101010101111111111100000000000
6: 0000000000000101010101011111111111110000000000000
7: 000000000000000101010101010111111111111111000000000000000
8: 00000000000000000101010101010101111111111111111100000000000000000
9: 000000000000000000010110010101011111111111111111110011000000100000000000000

Crossrefs

Sequence in context: A050797 A103967 A032400 * A004621 A014209 A202253

Adjacent sequences: A329419 A329420 A329421 * A329423 A329424 A329425

Keyword

nonn,more

Author

Jeffrey Shallit, Nov 30 2019

Status

approved