cp's OEIS Frontend

First differences of A001969. Observed by Franklin T. Adams-Watters, proved by Max Alekseyev, Aug 30 2006

0 is a, 1 is b and 2 is c. - Robert G. Wilson v, Jul 30 2018

Is there any interesting sequence b(n) such that b(n) mod 3 = a(n)?

Fixed point of the morphism 0->012; 1->1; 2->210 starting with a(0) = 0. - Philippe Deléham, Mar 14 2004

Also n such that A033485(n) == 3 (mod 4); see A007413.

Also n such that A029883(n-1) = -1, A036577(n-1) = 0, A036585(n-1) = 1. - Philippe Deléham, Mar 25 2004

The number of odd numbers before the n-th even number in this sequence is a(n). - Philippe Deléham, Mar 27 2004

Numbers n such that {A010060(n-1), A010060(n)}={1,0} where A010060 is the Thue-Morse sequence. - Benoit Cloitre, Jun 16 2006

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)

A concatenation of blocks u_k, k >= 0, where u_k has length 5^k. The sequence is defined recursively - see the Maple code.

From Kevin Ryde, Aug 11 2020: (Start)

Bollobás gives this sequence intending it to be a squarefree ternary word, where squarefree means nowhere a repeat w w for a block w of any length. However, squares do occur in it, for example a(18) onwards is 3212 3212, or a(19) onwards is 2123 2123.

In Bollobás' proof, the signs sequence is A337004. For blocks w of length l=4, the second signs subsequence presented (which should stop at length 7), does in fact occur, as does one other.

- - + + - - + \ two l=4 signs subsequences

- + + - - + + / in A337004 making squares here

All else in the argument holds, and in particular the "peaks" reduction means the only squares are lengths l = 4*5^k.

Zolotov shows this word is cubefree, and weakly squarefree (no x w w x where x is a single symbol and w is a block, possibly empty). However uniform cyclic squarefree must wait for Leech's order 13 morphism in A337005.

(End)

Conjecture: 3n - a(n) is in {0, 1} for all n >= 1.

From Michel Dekking, Sep 03 2019: (Start)

Proof of the conjecture by Kimberling: more is true. Here follows a proof of the formula below. Let T be the transform T(01)=0, T(1)=0.

Consider the return word structure of A285949 for the word 1:

A285949 = 0|1000|100|10|1000|10|100| ....

[See Justin & Vuillon (2000) for definition of return word. - N. J. A. Sloane, Sep 23 2019]

The three return words are u:=10, v:=100 and w:=1000. These words uniquely correspond to the conjugated three words u'=01, v'=010, w'=0100 in A285949, which are the unique images u'=T(0), v'=T(01) and w'=T(011) of the words 0, 01 and 011 in the Thue-Morse word A010060. The images of these three words under the Thue-Morse morphism 0->01, 1->10 are 01, 0110 and 011010, and we have

T(01)=010, T(0110)=010001, T(011010)=010001001.

Shifting by 1 in A285949, these correspond uniquely to the conjugated words 100, 100010, and 100010010. It follows that the Thue-Morse morphism induces the morphism u->v, v->wu, w->wvu on the return words.

This morphism is modulo a change of alphabet equal to the ternary Thue-Morse morphism with fixed point A007413.

Note that on the alphabet {4,3,2} of the respective lengths of w, v, and u we obtain the sequence (a(n+1)-a(n)) = 4,3,2,4,2,3,4,3,2,... of first differences of the positions of the 1's in A285949.

To prove the formula a(n) = A010060(n)+ 3n-1, it suffices to show that a(n+1)-a(n) = A010060(n+1)-A010060(n)+3.

That this indeed is true: see the Comments of A029883, the first differences of the standard form of the Thue-Morse sequence A001285.

(End)

Lexicographically ordered list of words of increasing length L=1,2,3,... over the alphabet {0,1,2}, excluding those which contain two adjacent subsequences with the same multiset of symbols regardless of internal order. E.g., 0,0 or 1,1 or 2,2 or 0,1,0,1 or 0,1,2,1,0,2, etc.

Peter Lawrence, Sep 06 2011: In other words, this is the sequence of all possible lists over the letters "0", "1", "2", such that within a list no two adjacent segments of any length contain the same multiset of symbols, first sorted by length of list, second lists of same length are sorted lexicographically. Recursively, to each list of length N create up to two lists of length N+1 by appending the two letters that are different from the last letter of the first list, and then check for and eliminate longer abelian squares; keeping all the lists sorted as in the previous description.

The number of sequences of the successive lengths are 3, 6, 12, 18, 30, 30, 18, for total row lengths of 3, 12, 36, 72,150, 180, 126.