cp's OEIS Frontend

A005713 Define strings S(0)=0, S(1)=11, S(n) = S(n-1)S(n-2); iterate.

%I A005713 #55 Mar 29 2023 14:51:27
%S A005713 1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,
%T A005713 1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,
%U A005713 1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,0,1
%N A005713 Define strings S(0)=0, S(1)=11, S(n) = S(n-1)S(n-2); iterate.
%C A005713 a(A035336(n)) = 0. - _Reinhard Zumkeller_, Dec 30 2011
%C A005713 a(n) = 1 - A123740(n).  This can be seen as follows. Define words T(0)=0, T(1)=1, T(n) = T(n-1)T(n-2). Then T(infinity) is the binary complement of the infinite Fibonacci word A003849. Obviously S(n) is the [1->11] transform of T(n). The claim now follows from the observation (see Comments of A123740) that doubling the 0's in the infinite Fibonacci word A003849 gives A123740. - _Michel Dekking_, Oct 21 2018
%C A005713 From _Michel Dekking_, Oct 22 2018: (Start)
%C A005713 Here is a proof of Cloitre's (corrected) formula
%C A005713       a(n) = abs(A014677(n+1)).
%C A005713 Since abs(-1) = abs(1) = 1, one has to prove that A014677(k)=0 if and only if there is an n such that AB(n) = k (using that a(n) = 1 - A123740(n)). Now A014677 is the sequences of first differences of A001468, and the 0's in A014677 occur if and only if there occurs a block 22 in A001468, which is given by
%C A005713       A001468(n) = floor((n+1)*phi) - floor(n*phi), n >= 0.
%C A005713 But then
%C A005713       A001468(n) = A014675(n-1), n > 0.
%C A005713 The sequence A014675 is fixed point of the morphism 1->2, 2->21, which is alphabet equivalent to the morphism 1->12, 2->1, the classical Fibonacci morphism in standard form. This implies that the 22 blocks in A001468 occur at position n+1 in if and only if 3 occurs in the fixed point A270788 of the 3-symbol Fibonacci morphism at k, which happens if and only if there is an n such that AB(n)=k (see Formula of A270788). (End)
%H A005713 Reinhard Zumkeller, <a href="/A005713/b005713.txt">Table of n, a(n) for n = 0..10000</a>
%H A005713 R. K. Guy, <a href="/A005712/a005712.pdf">Letter to N. J. A. Sloane, 1987</a>
%H A005713 Jeffrey Shallit and Anatoly Zavyalov, <a href="https://arxiv.org/abs/2303.15203">Transduction of Automatic Sequences and Applications</a>, arXiv:2303.15203 [cs.FL], 2023, see p. 31.
%F A005713 From _Benoit Cloitre_, Apr 21 2003: (Start)
%F A005713 For n > 1, a(n-1) = floor(phi*ceiling(n/phi)) - ceiling(phi*floor(n/phi)) where phi=(1+sqrt(5))/2.
%F A005713 For n >= 0, a(n) = abs(A014677(n+1)). (End)
%e A005713 The infinite word is S(infinity) = 110111101101111011110110...
%t A005713 s[0] = {0}; s[1] = {1, 1}; s[n_] := s[n] = Join[s[n-1], s[n-2]]; s[10] (* _Jean-François Alcover_, May 15 2013 *)
%t A005713 nxt[{a_,b_}]:={b,Join[a,b]}; Drop[Nest[nxt,{{0},{1,1}},10][[1]],3] (* _Harvey P. Dale_, Jan 31 2019 *)
%o A005713 (PARI) a(n,f1,f2)=local(f3); for(i=3,n,f3=concat(f2,f1); f1=f2; f2=f3); f2
%o A005713 (PARI) printp(a(10,[ 0 ],[ 1,1 ])) \\ Would give S(10). Sequence is S(infinity).
%o A005713 (Haskell)
%o A005713 a005713 n = a005713_list !! n
%o A005713 a005713_list = 1 : 1 : concat (sibb [0] [1,1]) where
%o A005713    sibb xs ys = zs : sibb ys zs where zs = xs ++ ys
%o A005713 -- _Reinhard Zumkeller_, Dec 30 2011
%Y A005713 Cf. A005614, A003849.
%Y A005713 Cf. A001468, A014675, A014677, A123740, A270788.
%K A005713 nonn,easy,nice
%O A005713 0,1
%A A005713 _N. J. A. Sloane_
%E A005713 Corrected by _Michael Somos_