

A085794


Lexicographically earliest squarefree infinite ternary word.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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 ThueMorse 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 JeanPaul Allouche.]  M. F. Hasler, Nov 29 2019
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)


REFERENCES

JeanPaul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003, page 30.


LINKS



EXAMPLE

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 ThueMorse 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)


PROG

(PARI) A085794_upto(n, A)={ for(n=1+#A+!A, #A=Vec(A, n+2), while( A[n]==A[n1], while( A[n]++>2, A[n]=0; n)); for(L=2, (n1)\2, A[nL..n1]!=A[n2*L..nL1]  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


CROSSREFS



KEYWORD

nonn


AUTHOR

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


EXTENSIONS



STATUS

approved



