login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

REFERENCES

Jean-Paul 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 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

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 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 7 02:39 EDT 2020. Contains 333292 sequences. (Running on oeis4.)