A085794 Lexicographically earliest squarefree infinite ternary word.

0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1

Offset: 0

Author

Claude Lenormand (claude.lenormand(AT)free.fr), Jul 24 2003; corrected Jul 25 2003

Keywords

• nonn

Comments

Open Problem 1.10.2 in the Allouche & Shallit reference asks for a good alternate characterization of this sequence. (Is it morphic, if so for which morphism?)

The sequence cannot be constructed in a greedy way (without backtracking) choosing each a(n) simply such that the sequence is squarefree: After (0, 1, 0, 2, 0, 1) the greedy choice would be to append 0, but then one is stuck for the alphabet {0,1,2}. If the alphabet is infinite, this greedy procedure yields A007814. - M. F. Hasler, Nov 28 2019

We know that an infinite ternary squarefree word exists, namely the ternary Thue-Morse sequence A036580 = A007413(.+1) - 1. The space of squarefree words is closed (limit of a sequence of squarefree words is again squarefree, using e.g. topology induced by d(x,y) = Sum_{k>=0} |x_k - y_k|/3^k or exp(-min{k: x_k != y_k})) and compact, so the inf exists and is reached for some element. [Thanks to Jean-Paul Allouche.] - M. F. Hasler, Nov 29 2019

From Thomas Anton, May 01 2022: (Start)

A direct proof of this is as follows: as noted above we may obtain the sequence through a greedy algorithm with backtracking. This process eliminates as a prefix for any squarefree word, any word lexicographically earlier than an initial segment of this word. Since distinct words must have distinct prefixes of some length, any other squarefree word must be lexicographically later.

Additionally, it is not necessary to show that the inf exists since lexicographically ordered infinite words on a finite alphabet form a complete total ordering. (End)

Examples

			From _M. F. Hasler_, Nov 29 2019: (Start)
After a(0) = 0 one must have a(1) = 1 because 00 is not squarefree, i.e., it has a subsequence X = 0 such that XX = 00 is also a subsequence.
After (0,1) one has again a(2) = 0, but then a(3) must be different from 0 (to avoid 00) and from 1 to avoid XX with X = 01, so a(3) = 2.
Then again a(4) = 0 and a(5) = 1.
Now it looks that a(6) could be equal to 0, but with this choice, there would be no possible choice for a(7): all in {0, 1, 2} would produce a square subsequence, in the last case with X = 0102. Since 1 is also excluded, a(6) = 2 is the only possible choice.
A partial subsequence a(0..k) is correct if one can append the infinite ternary Thue-Morse word A036580 and the result is squarefree. (Sufficient but obviously not necessary condition, consider a(k) = A036580(0).) To ensure this, one needs only to check up to twice the length of the prefixed subsequence. (End)
		

References

• Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003, page 30.

Links

• Eric Rowland, Table of n, a(n) for n = 0..16383 [These terms are conjectural.]

Crossrefs

Cf. A036580, A007413.

Programs

PARI

A085794_upto(n,A)={ for(n=1+#A+!A,#A=Vec(A,n+2), while( A[n]==A[n-1], while( A[n]++>2, A[n]=0; n--)); for(L=2,(n-1)\2, A[n-L..n-1]!=A[n-2*L..n-L-1] || while(A[n]++>2, A[n]=0; n--) || !n-- || next(2))); A[^-1]} \\ Returns a(0..n). Optional arg allows to specify starting value(s). - M. F. Hasler, Nov 29 2019

Extensions

More terms from John W. Layman, May 18 2004

Changed b-file to an a-file. - N. J. A. Sloane, Mar 26 2019