

A085794


Lexicographic minimal 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 square free: 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


REFERENCES

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


LINKS

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


EXAMPLE

From M. F. Hasler, Nov 29 2019:
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

Cf. A036580, A007413.
Sequence in context: A331534 A035445 A053603 * A239002 A004548 A125921
Adjacent sequences: A085791 A085792 A085793 * A085795 A085796 A085797


KEYWORD

nonn


AUTHOR

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


EXTENSIONS

More terms from John W. Layman, May 18 2004
Changed bfile to an afile.  N. J. A. Sloane, Mar 26 2019


STATUS

approved



