A285960 - OEIS

%I #11 Apr 20 2022 00:05:00

%S 1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1,1,

%T 1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,

%U 1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1

%N {01->1}-transform of the Thue-Morse word A010060.

%C From _Michel Dekking_, Apr 19 2022: (Start)

%C This sequence is a morphic sequence,  i.e., the letter-to-letter image of the fixed point of a morphism mu. Here is a proof.

%C The Thue-Morse sequence x:=A010060 is a concatenation of the four return words  A=011, B=010, C=0110,  and  D=01,  of  the word 01 in x. (These are the words occurring in x starting with 01, and having no other occurrences of 01 in them).  By applying the Thue-Morse morphism 0->01, 1->10 to the return words one induces the derived morphism

%C       tau:  A -> AB, B -> CD, C -> ABD, D -> C.

%C It is clear that to obtain (a(n)) from x one has to apply the morphism delta to x written as ABCDABD... given by

%C     A-> 11, B-> 10, C-> 110, D-> 1.

%C In the paper  "Morphic words, Beatty sequences and integer images of the Fibonacci language" delta is called a decoration map. It is well-known that decorated fixed points are morphic sequences, and the 'natural' algorithm to achieve this yields a morphism on an alphabet of 2+2+3+1 = 8 symbols. In this particular case one can reduce the number of symbols to 4, say {a,b,c,d}, and obtain the morphism mu

%C     mu:  a->ab, b->cd, c->abd, d->c.

%C Let y be the fixed point of mu starting with the letter  a. Then (a(n)) = lambda(y), where the letter-to-letter map lambda is defined by

%C     lambda:  a->1, b->1, c->1, d->0.

%C Proof of the bisection formula below: the derived morphisms for the return words of 01, respectively 011 in A285960 and A286046 both are the same morphism tau. Moreover, the decoration morphism A-> 11, B-> 10, C-> 110, D-> 1 to obtain (a(n)) corresponds exactly to the letters in the decoration morphism A-> 1010, B-> 1001, C-> 101001, D->10 occurring at the odd positions. This implies a(n) = A286046(2n-1), n = 1,2,...

%C (End)

%H Clark Kimberling, <a href="/A285960/b285960.txt">Table of n, a(n) for n = 1..10000</a>

%H M. Dekking, <a href="https://doi.org/10.1016/j.tcs.2019.12.036">Morphic words, Beatty sequences and integer images of the Fibonacci language</a>, Theoretical Computer Science  809,  407-417 (2020).

%F a(n) = A286046(2n-1), n = 1,2,...

%e As a word, A010060 = 0110100110010110100101100..., and replacing each 01 by 1 gives 1110110111101110111011011101110...

%t s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 8] (* Thue-Morse, A010060 *)

%t w = StringJoin[Map[ToString, s]]

%t w1 = StringReplace[w, {"01" -> "1"}]

%t st = ToCharacterCode[w1] - 48 (* A285960  *)

%t Flatten[Position[st, 0]]  (* A285961 *)

%t Flatten[Position[st, 1]]  (* A285962 *)

%Y Cf. A010060, A285961, A285962, A286046.

%K nonn,easy

%O 1

%A _Clark Kimberling_, May 05 2017