login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A104324 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n. 10

%I

%S 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 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 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 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n.

%C 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 This sequence has some interesting fractal properties (plot it!).

%C 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 Read mod 2 gives the Fibonacci word A003849. The differences, halved, give A213911.

%D 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 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 Amy Glen, Jamie Simpson, 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 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 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 Jiemeng Zhang, Zhixiong Wen, Wen Wu, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p52">Some Properties of the Fibonacci Sequence on an Infinite Alphabet</a>, Electronic Journal of Combinatorics, 24(2) (2017), #P2.52.

%F a(n) = A007895(n) + A213911(n). - _Reinhard Zumkeller_, Mar 10 2013

%e 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 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 0,

%e 1,

%e 2,2,

%e 3,2,3,

%e 4,2,3,4,4,

%e 5,2,3,4,4,5,4,5,

%e 6,2,3,4,4,5,4,5,6,4,5,6,6,

%e 7,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,

%e 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 ... (see also A288576). - _N. J. A. Sloane_, Jun 30 2017

%p 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 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 *)

%o (Haskell)

%o import Data.List (group)

%o a104324 = length . map length . group . a213676_row

%o -- _Reinhard Zumkeller_, Mar 10 2013

%o (PARI) phi(n) = if (n%2, n+1, [n, n+1]);

%o vphi(v) = nv = []; for (k=1, #v, nv = concat(nv, phi(v[k]));); nv;

%o lista(nn) = {v = [0]; for (i=1, nn, v = vphi(v);); v;} \\ _Michel Marcus_, Oct 10 2017

%Y Cf. A007895, A014417, A104325, A189920, A213676, A213911.

%Y See also the Fibonacci word A003849.

%Y For partial sums see A288575.

%Y See A288576 for another view of the initial blocks.

%K nonn,look,changed

%O 0,3

%A _Ron Knott_, Mar 01 2005

%E Entry revised by _N. J. A. Sloane_, Jun 30 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 17:39 EDT 2017. Contains 293648 sequences.