A284620 - OEIS

%I #24 Mar 17 2020 12:14:37

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

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

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

%N {00->2}-transform of the infinite Fibonacci word A003849.

%C From _Michel Dekking_, Mar 17 2020: (Start)

%C This sequence is a morphic sequence, i.e., the letter-to-letter image of the fixed point of a morphism mu. In fact, one can take the alphabet {A,B,C,D} with the morphism

%C       mu:   A->AB, B->CD, C->ABCD, D->CD,

%C and the letter-to-letter map lambda defined by

%C     lambda:  A->0, B->1, C->2, D->1.

%C Then (a(n)) = lambda(x), where x = ABCDABCDCD... is the unique fixed point of the morphism mu.

%C How does one see this? The infinite Fibonacci word

%C       x_F = A003849 = 0100101001001....

%C can be written as a concatenation of the two words 01 and 001.

%C In fact, if beta is the Fibonacci morphism 0->01, 1->0, then beta(01)=010, beta(001)=01010, from which this can be read off.

%C This can also be found in Lemma 23 in Allouche and Dekking, which gives, moreover, that if we define the morphism g on the alphabet {a,b} by

%C       g(a) = ab, g(b) =abb

%C then a(n) = delta(x_G(n)), where

%C       x_G = ababbababb...

%C is the unique fixed point of g, and delta is the map

%C       delta(a) = 01, delta(b) = 21.

%C In my paper "Morphic words,..." such a map delta is called a decoration.

%C It is well-known that decorated fixed points are morphic sequences, and the 'natural' algorithm to achieve this splits a in AB, and b in CD. This gives the morphism mu on the alphabet {A,B,C,D}, and the letter-to-letter map lambda.

%C We next prove the first conjecture by Kimberling. We easily see from the form of mu that the letters B and D occur, and only occur, at even positions in the fixed point x of mu. Since lambda(B)=lambda(D)=1, and A and C are not mapped to 1, it follows immediately that the positions of 1 in (a(n)) are given by A005843 = (2n).

%C For a proof of Kimberling's second conjecture, note that a(n)=2  iff  x(n)=C, where x is the fixed point of mu.  The return words of C in x are CD and CDAB.  Coding these two return words by their lengths, mu induces a descendant morphism tau given by

%C       tau(2) = 24, tau(4) = 244.

%C We see that tau is just an alphabet change of the morphism g. Let t = 2424424244... be the unique fixed point of tau.  It is well-known (see, e.g., Lemma 12 in "Morphic words,..."), that t = 2 x_F, where x_F =  x_F(4,2) now is the Fibonacci word on the alphabet {4,2}. The partial sums of  x_F(4,2) are equal to the generalized  Beatty sequence V  given by

%C       V(n) =  2*floor(n*phi) + 1,

%C according to Lemma 8 in the Allouche and Dekking paper.

%C This proves Kimberling's conjecture, provided we give the sequence A130568 offset 1, as we should.

%C (End)

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

%H J.-P. Allouche, F. M. Dekking, <a href="https://doi.org/10.2140/moscow.2019.8.325">Generalized Beatty sequences and complementary triples</a>, Moscow Journal of Combinatorics and Number Theory 8, 325-341 (2019).

%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).

%e As a word, A003849 = 01001010010010100..., and replacing each 00 by 2 gives 012101212101210...

%t s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 13]  (* A003849 *)

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

%t w1 = StringReplace[w, {"00" -> "2"}]

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

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

%t Flatten[Position[st, 1]]  (* A005843 - conjectured *)

%t Flatten[Position[st, 2]]  (* A130568 - conjectured *)

%Y Cf. A003849, A005843, A130568, A284621, A284749.

%K nonn,easy

%O 1,3

%A _Clark Kimberling_, May 02 2017