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

%I #30 Sep 08 2022 08:46:19

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

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

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

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

%C From _Michel Dekking_, Oct 11 2017: (Start)

%C (a(n)) is the homogeneous Sturmian sequence with slope r = (15 + sqrt(5))/22.

%C Note that (a(n)) can be obtained as the binary complement of the sequence a~ produced by applying the morphism gamma: 0->001, 1->0 to the binary complement x of the Fibonacci word A003849. One has x = A005614, the infinite Fibonacci word generated by 0->1, 1->10. Moreover, gamma can be written as a composition gamma = psi_3 psi_1 of the two elementary Sturmian morphisms psi_1: 0->01, 1->0 (standard Fibonacci), and psi_3: 0->0, 1->01. This implies immediately that a~ = gamma(x) is Sturmian, and to get the slope, use Lemma 2.2.18 in Lothaire, which gives that the Sturmian word b := psi_1(x) has slope (2-phi)/(3-phi) = (5-sqrt(5))/10 (b = A221150), and next a~ = psi_3(b) has slope 1/(3+phi) = (7 - sqrt(5))/22. Thus (a(n)) has slope 1- (7-sqrt(5))/22 = (15 + sqrt(5))/22.

%C (End)

%C The algebraic conjugate t = (15 - sqrt(5))/22 of r lies in (0,1), so by Allauzen's criterion, (a(n)) is NOT a fixed point of a morphism. - _Michel Dekking_, Oct 11 2017

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

%H M. Lothaire, <a href="http://tomlr.free.fr/Math%E9matiques/Fichiers%20Claude/Auteurs/aaaDivers/Lothaire%20-%20Algebraic%20Combinatorics%20On%20Words.pdf">Algebraic combinatorics on words</a>, Cambridge University Press. Online publication date: April 2013; Print publication year: 2002.

%F a(n) = floor((n+1)*r) - floor(nr), where r = (15 + sqrt(5))/22. - _Michel Dekking_, Oct 11 2017

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

%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" -> "110"}]

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

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

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

%t Table[Floor[(n + 1) (15 + Sqrt[5]) / 22] - Floor[n (15 + Sqrt[5]) / 22], {n, 100}] (* _Vincenzo Librandi_, Ovt 15 2017 *)

%o (Magma) [Floor((n+1)*(15+Sqrt(5))/22)-Floor(n*(15+Sqrt(5))/22): n in [1..100]]; // _Vincenzo Librandi_, Oct 15 2017

%Y Cf. A005614, A221150, A276855, A287770.

%K nonn,easy

%O 1

%A _Clark Kimberling_, Jun 03 2017