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

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, 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, 0, 1, 2, 1, 0, 1, 2, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1

Offset

1,3

Comments

From Michel Dekking, Mar 17 2020: (Start)

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

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

and the letter-to-letter map lambda defined by

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

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

How does one see this? The infinite Fibonacci word

x_F = A003849 = 0100101001001....

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

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.

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

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

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

x_G = ababbababb...

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

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

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

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.

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

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

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

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

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

according to Lemma 8 in the Allouche and Dekking paper.

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

(End)

Links

Clark Kimberling, Table of n, a(n) for n = 1..10000

J.-P. Allouche, F. M. Dekking, Generalized Beatty sequences and complementary triples, Moscow Journal of Combinatorics and Number Theory 8, 325-341 (2019).

M. Dekking, Morphic words, Beatty sequences and integer images of the Fibonacci language, Theoretical Computer Science 809, 407-417 (2020).

Example

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

Mathematica

s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 13]  (* A003849 *)
w = StringJoin[Map[ToString, s]]
w1 = StringReplace[w, {"00" -> "2"}]
st = ToCharacterCode[w1] - 48 (* A284620 *)
Flatten[Position[st, 0]]  (* A284621 *)
Flatten[Position[st, 1]]  (* A005843 - conjectured *)
Flatten[Position[st, 2]]  (* A130568 - conjectured *)

Crossrefs

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

Sequence in context: A241062 A333471 A360711 * A038698 A333590 A263233

Adjacent sequences: A284617 A284618 A284619 * A284621 A284622 A284623

Keyword

nonn,easy

Author

Clark Kimberling, May 02 2017

Status

approved