cp's OEIS Frontend

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

%I A284620 #30 May 23 2025 12:07:11
%S A284620 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 A284620 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 A284620 0,1,2,1,0,1,2,1,2,1,0,1,2,1,0,1,2,1
%N A284620 {00->2}-transform of the infinite Fibonacci word A003849.
%C A284620 From _Michel Dekking_, Mar 17 2020: (Start)
%C A284620 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 A284620       mu:   A->AB, B->CD, C->ABCD, D->CD,
%C A284620 and the letter-to-letter map lambda defined by
%C A284620     lambda:  A->0, B->1, C->2, D->1.
%C A284620 Then (a(n)) = lambda(x), where x = ABCDABCDCD... is the unique fixed point of the morphism mu.
%C A284620 How does one see this? The infinite Fibonacci word
%C A284620       x_F = A003849 = 0100101001001....
%C A284620 can be written as a concatenation of the two words 01 and 001.
%C A284620 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 A284620 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 A284620       g(a) = ab, g(b) =abb
%C A284620 then a(n) = delta(x_G(n)), where
%C A284620       x_G = ababbababb...
%C A284620 is the unique fixed point of g, and delta is the map
%C A284620       delta(a) = 01, delta(b) = 21.
%C A284620 In my paper "Morphic words,..." such a map delta is called a decoration.
%C A284620 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 A284620 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 A284620 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 A284620       tau(2) = 24, tau(4) = 244.
%C A284620 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 A284620       V(n) = 2*floor(n*phi) + 1,
%C A284620 according to Lemma 8 in the Allouche and Dekking paper.
%C A284620 This proves Kimberling's conjecture, provided we give the sequence A130568 offset 1, as we should.
%C A284620 (End)
%H A284620 Clark Kimberling, <a href="/A284620/b284620.txt">Table of n, a(n) for n = 1..10000</a>
%H A284620 J.-P. Allouche and 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 A284620 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 A284620 As a word, A003849 = 01001010010010100..., and replacing each 00 by 2 gives 012101212101210...
%t A284620 s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 13]  (* A003849 *)
%t A284620 w = StringJoin[Map[ToString, s]]
%t A284620 w1 = StringReplace[w, {"00" -> "2"}]
%t A284620 st = ToCharacterCode[w1] - 48 (* A284620 *)
%t A284620 Flatten[Position[st, 0]]  (* A284621 *)
%t A284620 Flatten[Position[st, 1]]  (* A005843 - conjectured *)
%t A284620 Flatten[Position[st, 2]]  (* A130568 - conjectured *)
%o A284620 (Python)
%o A284620 from math import isqrt
%o A284620 def A130568(n): return (n+isqrt(5*n**2)&-2)|1
%o A284620 def A284620(n):
%o A284620     def bsearch(f, n):
%o A284620         kmin, kmax = 0, 1
%o A284620         while f(kmax) <= n:
%o A284620             kmax <<= 1
%o A284620         kmin = kmax>>1
%o A284620         while True:
%o A284620             kmid = kmax+kmin>>1
%o A284620             if f(kmid) > n:
%o A284620                 kmax = kmid
%o A284620             else:
%o A284620                 kmin = kmid
%o A284620             if kmax-kmin <= 1:
%o A284620                 break
%o A284620         return kmin
%o A284620     return (2 if n>1 and A130568(bsearch(A130568,n))==n else 0) if n&1 else 1 # _Chai Wah Wu_, May 22 2025
%Y A284620 Cf. A003849, A005843, A130568, A284621, A284749.
%K A284620 nonn,easy
%O A284620 1,3
%A A284620 _Clark Kimberling_, May 02 2017