login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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)
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.]
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 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)
PROG
(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
CROSSREFS
Sequence in context: A035445 A053603 A371222 * A336939 A239002 A004548
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 b-file to an a-file. - N. J. A. Sloane, Mar 26 2019
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:13 EDT 2024. Contains 371265 sequences. (Running on oeis4.)