A309623 Numbers k for which there is an extremal ternary word of length k.

25, 41, 48, 50, 63

Offset: 1

Author

Jeffrey Shallit, Oct 20 2019

Keywords

• nonn
• more

Comments

A ternary word is one over a three-letter alphabet, such as {0,1,2}. Such a word is called "squarefree" if it contains no subblock of the form XX, where X is a nonempty contiguous block. A word x is extremal if it is squarefree, but every possible insertion of a single letter, that is, every word of the form x' a x'' with x = x' x'', a in {0,1,2}, is not squarefree.

The Grytczuk paper proves there are arbitrarily long extremal words.

Examples

			The smallest extremal word is of length 25, which is 0120102120121012010212012 and is unique up to renaming of the letters. The next smallest are of length 41, and there are two (up to renaming), namely 01021012021020121021201021012021020121021 and 02102012102120102101202102012102120102101. The next is of length 48, and is unique (up to renaming): 010212012102010212012101202120121020102120121020. The next is of length 50 and is unique (up to renaming): 01021201021012021020121012021201021012021020121020.
The next smallest are of length 63, and there are two (up to renaming): 010210120210201021202102012102120102101202102010212021020121021, 012010212012101202120121020120210120102120121012021201210201202. - _Michael S. Branicky_, May 06 2022
For lengths 25, 41, 48, 50, and 63, there is a unique extremal word up to both renaming and reversal. - _Pontus von Brömssen_, May 07 2022
		

Links

• J. Grytczuk, H. Kordulewski, and A. Niewadomski, Extremal square-free words, arxiv preprint arXiv:1910.06226v1 [math.CO], October 14 2019.
• Jaroslaw Grytczuk, Hubert Kordulewski, and Artur Niewiadomski, Extremal Square-Free Words, Electronic J. Combinatorics, 27 (1), 2020, #1.48.

Crossrefs

Cf. A006156, A332605.

Extensions

a(5) from Michael S. Branicky, May 06 2022