login
{0->1, 1->001}-transform of the infinite Fibonacci word A003849.
4

%I #23 Sep 30 2023 09:17:50

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

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

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

%N {0->1, 1->001}-transform of the infinite Fibonacci word A003849.

%C Appears to be the same as A286749 shifted by one place/index. - _R. J. Mathar_, Jun 14 2017

%C From _Michel Dekking_, Sep 05 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 {1,2,3,4} with the morphism

%C mu: 1->12341, 2->1, 3->2, 4->34,

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

%C g: 1->1, 2->0, 3->0, 4->1.

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

%C In my paper "Morphic words, Beatty sequences and integer images of the Fibonacci language" the transform map 0->1, 1->001 is called a decoration. 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 1+3 = 4 symbols. In general there are several choices for mu. Here we have chosen mu such that it is the SAME morphism as used to generate A286749 as a morphic sequence.

%C This will make it possible to prove the remarkable conjecture by _R. J. Mathar_ from June 14, 2017. Note that A286749 is a letter-to-letter projection of the SAME sequence x = 123411234... but by a different letter-to-letter map f:

%C f: 1->1, 2->1, 3->0, 4->0.

%C How does one prove that A286749(n+1) = a(n), for n > 0?

%C The crucial observation is that x is a concatenation of the two words 12341 and 1234. This follows directly from mu(12341) = 12341123412341, and mu(1234) = 123411234. Next one observes that

%C f(12341) = 11001 = 1g(12341)1^{-1},

%C f(1234) = 1100 = 1g(1234)1^{-1}.

%C This property implies then that A286749(n+1) = a(n).

%C (End)

%H Clark Kimberling, <a href="/A287674/b287674.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).

%e As a word, A003849 = 0100101001001010010100100..., and replacing each 0 by 1 and each 1 by 001 gives 100111001100111001110011001...

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

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

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

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

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

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

%Y Cf. A003849, A286749, A287675, A287676.

%K nonn,easy

%O 1

%A _Clark Kimberling_, Jun 02 2017