|
%I #17 Apr 24 2023 15:19:29
%S 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,1,1,
%T 0,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,
%U 0,1,1,0,0,1,1,1,0,0,1,1,1,0,0,1,1,0
%N {0100->null}-transform of the infinite Fibonacci word A003849.
%C As a word, A003849 = 01001010010010100101001001010010..., and deleting each occurrence of 0100 gives 11001110011001110011010..., in which the positions of 0 are given by A286750, and of 1, by A286751.
%C From _Michel Dekking_, Aug 29 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 lambda defined by
%C lambda: 1->1, 2->1, 3->0, 4->0.
%C Then (a(n)) = lambda(x), where x = 123412... is the unique fixed point of the morphism mu.
%C How does one see this? We note first that the {0100->null}-transform is equivalent to the {01001->1}-transform, since 000 does not occur in the Fibonacci word xF:=A003849. This indicates that we should look at the return words of the word 01001 in xF. These are the two words a:=01001 and b:=010. The main result of the Huang and Wen paper is that these two words occur exactly as the Fibonacci word itself.
%C The situation is somewhat awkward for the word 01001, Huang and Wen call this 'overlapped return words'. To get rid of this overlap nuisance we consider rather the concatenation of the words a=01001 and ba=01001001 in xF over the alphabet {a,b}. Then the {01001->1}-transform maps a to 1, and ba to 1001.
%C But then we might as well map a to 1 and b to 100. This is what I call a decoration of xF. It is well-known that decorated fixed points are morphic sequences, and there is a 'natural' algorithm to achieve this.
%C Here this is performed by tripling the letter b, to say, the three letters 234 and coding a by 1. One first writes the induced block-map:
%C 1->12341, 234->1234,
%C and then turns this into the morphism
%C 1->12341, 2->1, 3->2, 4->34.
%C The letter-to-letter map is given by lambda: 1->1, 2->1, 3->0, 4->0.
%C (End)
%H Clark Kimberling, <a href="/A286749/b286749.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).
%H Y. Huang and Z.-Y. Wen, <a href="https://doi.org/10.1016/j.tcs.2015.05.048">The sequence of return words of the Fibonacci sequence</a>, Theoretical Computer Science 593, 106-116 (2015).
%t s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 12]; (* A003849 *)
%t w = StringJoin[Map[ToString, s]];
%t w1 = StringReplace[w, {"0100" -> ""}]; st = ToCharacterCode[w1] - 48; (* A286749 *)
%t Flatten[Position[st, 0]]; (* A286750 *)
%t Flatten[Position[st, 1]]; (* A286751 *)
%Y Cf. A003849, A286750, A286751.
%K nonn,easy
%O 1
%A _Clark Kimberling_, May 14 2017
|
