cp's OEIS Frontend

A104324 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n.

%I A104324 #72 Apr 05 2024 10:04:00
%S A104324 0,1,2,2,3,2,3,4,2,3,4,4,5,2,3,4,4,5,4,5,6,2,3,4,4,5,4,5,6,4,5,6,6,7,
%T A104324 2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,8,2,3,4,4,5,4,5,6,4,5,6,6,7,
%U A104324 4,5,6,6,7,6,7,8,4,5,6,6,7,6,7,8,6,7,8,8,9,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6
%N A104324 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n.
%C A104324 Image of 0 under repeated application of the morphism phi = {2i -> 2i,2i+1; 2i+1 -> 2i+2: i = 0,1,2,3,...}. - _N. J. A. Sloane_, Jun 30 2017
%C A104324 This sequence has some interesting fractal properties (plot it!).
%C A104324 First occurrence of k=0,1,2,... is at 0,1,2,4,7,12,20,33,54, ..., A000071(k+1): Fibonacci numbers - 1. - _Robert G. Wilson v_, Apr 25 2006
%C A104324 Read mod 2 gives the Fibonacci word A003849. The differences, halved, give A213911.
%D A104324 E. Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.
%H A104324 N. J. A. Sloane, <a href="/A104324/b104324.txt">Table of n, a(n) for n = 0..28656</a> [First 10000 terms from Reinhard Zumkeller]
%H A104324 Amy Glen, Jamie Simpson, and W. F. Smyth, <a href="https://arxiv.org/abs/1710.02782">More properties of the Fibonacci word on an infinite alphabet</a>, arXiv:1710.02782 [math.CO], 2017.
%H A104324 Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html">Using Fibonacci Numbers to Represent Whole Numbers</a>
%H A104324 Casey Mongoven, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from175to192.pdf">Sonification of multiple Fibonacci-related sequences</a>, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.
%H A104324 Jiemeng Zhang, Zhixiong Wen, and Wen Wu, <a href="https://doi.org/10.37236/6745">Some Properties of the Fibonacci Sequence on an Infinite Alphabet</a>, Electronic Journal of Combinatorics, 24(2) (2017), #P2.52.
%F A104324 a(n) = A007895(n) + A213911(n). - _Reinhard Zumkeller_, Mar 10 2013
%e A104324 14 = 13+1 as a sum of Fibonacci numbers = 100001(in Fibonacci base) using the least number of 1's (Zeckendorf Rep): it consists of 3 runs: one 1, four 0's, one 1, so a(14)=3.
%e A104324 This sequence may be broken up into blocks of lengths 1,1,2,3,5,8,... (the nonzero Fibonacci numbers). The first occurrence of a number indicates the start of a new block. The first few blocks are:
%e A104324 0,
%e A104324 1,
%e A104324 2,2,
%e A104324 3,2,3,
%e A104324 4,2,3,4,4,
%e A104324 5,2,3,4,4,5,4,5,
%e A104324 6,2,3,4,4,5,4,5,6,4,5,6,6,
%e A104324 7,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,
%e A104324 8,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,8,4,5,6,6,7,6,7,8,6,7,8,8,
%e A104324 ... (see also A288576). -  _N. J. A. Sloane_, Jun 30 2017
%p A104324 with(combinat,fibonacci):fib:=fibonacci: zeckrep:=proc(N)local i,z,j,n;i:=2;z:=NULL;n:=N; while fib(i)<=n do i:=i+1 od;print(i=fib(i)); for j from i-1 by -1 to 2 do if n>=fib(j) then z:=z,1;n:=n-fib(j) else z:=z,0 fi od; [z] end proc: countruns:=proc(s)local i,c,elt;elt:=s[1];c:=1; for i from 2 to nops(s) do if s[i]<>s[i-1] then c:=c+1 fi od; c end proc: seq(countruns(zeckrep(n)),n=1..100);
%t A104324 f[n_Integer] := Block[{k = Ceiling[ Log[ GoldenRatio, n*Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; While[ fr[[1]] == 0, fr = Rest@fr]; Length@ Split@ fr]; Array[f, 105] (* _Robert G. Wilson v_, Apr 25 2006 *)
%t A104324 Nest[ReplaceAll[#, {t_ /; EvenQ[t] :> Sequence[t, t+1], t_ /; OddQ[t] :> t+1}] &, {0}, 10] (* _Paolo Xausa_, Apr 05 2024 *)
%o A104324 (Haskell)
%o A104324 import Data.List (group)
%o A104324 a104324 = length . map length . group . a213676_row
%o A104324 -- _Reinhard Zumkeller_, Mar 10 2013
%o A104324 (PARI) phi(n) = if (n%2, n+1, [n, n+1]);
%o A104324 vphi(v) = nv = []; for (k=1, #v, nv = concat(nv, phi(v[k]));); nv;
%o A104324 lista(nn) = {v = [0]; for (i=1, nn, v = vphi(v);); v;} \\ _Michel Marcus_, Oct 10 2017
%Y A104324 Cf. A007895, A014417, A104325, A189920, A213676, A213911.
%Y A104324 See also the Fibonacci word A003849.
%Y A104324 For partial sums see A288575.
%Y A104324 See A288576 for another view of the initial blocks.
%K A104324 nonn,look
%O A104324 0,3
%A A104324 _Ron Knott_, Mar 01 2005
%E A104324 Entry revised by _N. J. A. Sloane_, Jun 30 2017