

A309623


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


1




OFFSET

1,1


COMMENTS

A ternary word is one over a threeletter 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.


REFERENCES

Jaroslaw Grytczuk, Hubert Kordulewski, Artur Niewiadomski, Extremal SquareFree Words, Electronic J. Combinatorics, 27 (1), 2020, #1.48.


LINKS

Table of n, a(n) for n=1..4.
J. Grytczuk, H. Kordulewski, and A. Niewadomski, Extremal squarefree words, arxiv preprint arXiv:1910.06226v1 [math.CO], October 14 2019.


EXAMPLE

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.


CROSSREFS

Cf. A006156, A332605.
Sequence in context: A104667 A066844 A255608 * A242074 A195564 A147287
Adjacent sequences: A309620 A309621 A309622 * A309624 A309625 A309626


KEYWORD

nonn,more


AUTHOR

Jeffrey Shallit, Oct 20 2019


STATUS

approved



