cp's OEIS Frontend

A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.

%I A014417 #112 Jan 05 2025 19:51:34
%S A014417 0,1,10,100,101,1000,1001,1010,10000,10001,10010,10100,10101,100000,
%T A014417 100001,100010,100100,100101,101000,101001,101010,1000000,1000001,
%U A014417 1000010,1000100,1000101,1001000,1001001,1001010,1010000,1010001,1010010,1010100,1010101
%N A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.
%C A014417 Old name was: Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary vectors not containing 11.
%C A014417 For n > 0, write n = Sum_{i >= 2} eps(i) Fib_i where eps(i) = 0 or 1 and no 2 consecutive eps(i) can be 1 (see A035517); then a(n) is obtained by writing the eps(i) in reverse order.
%C A014417 "One of the most important properties of the Fibonacci numbers is the special way in which they can be used to represent integers. Let's write j >> k <==> j >= k+2. Then every positive integer has a unique representation of the form n = F_k1 + F_k2 + ... + F_kr, where k1 >> k2 >> ... >> kr >> 0. (This is 'Zeckendorf's theorem.') ... We can always find such a representation by using a "greedy" approach, choosing F_k1 to be the largest Fibonacci number =< n, then choosing F_k2 to be the largest that is =< n - F_k1 and so on. Fibonacci representation needs a few more bits because adjacent 1's are not permitted; but the two representations are analogous." [Concrete Math.]
%C A014417 Since the binary representation of n in base of Fibonacci numbers allows only the successive bit pairs 00, 01, 10 and leaves 11 unused, we can use a ternary representation using all trits 0, 1, 2 where 00 --> 0, 01 --> 1 and 10 --> 2 (e.g. binary 1001010 as ternary 1022). - _Daniel Forgues_, Nov 30 2009
%C A014417 The same sequence also arises when considering the NegaFibonacci representations of the integers, as follows. Take the NegaFibonacci representations of n = 0, 1, 2, ... (A215022) and of n = -1, -2, -3, ... (A215023), sort the union of these two lists into increasing binary order, and we get A014417. Likewise the corresponding list of decimal representations, A003714, is the union of A215024 and A215025 sorted into increasing order.  - _N. J. A. Sloane_, Aug 10 2012
%C A014417 Also, numbers, written in binary, such that no adjacent bits are equal to 1: A one-dimensional analog of the matrices considered in A228277/A228285, A228390, A228476, A228506 etc. - _M. F. Hasler_, Apr 27 2014
%C A014417 The sequence of final bits, starting with a(1), is the complement of the Fibonacci word A005614. - _N. J. A. Sloane_, Oct 03 2018
%C A014417 This representation is named after the Belgian Army doctor and mathematician Edouard Zeckendorf (1901-1983). - _Amiram Eldar_, Jun 11 2021
%D A014417 Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
%D A014417 Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
%D A014417 Edouard 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 A014417 T. D. Noe and Harry J. Smith, <a href="/A014417/b014417.txt">Table of n, a(n) for n = 0..10000</a>
%H A014417 Paul Dalenberg and Tom Edgar, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/56-2.html">Consecutive factorial base Niven numbers</a>, Fibonacci Quart., Vol. 56, No. 2 (2018), pp. 163-166.
%H A014417 Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf">Wythoff Wisdom</a>, 43 pages, no date, apparently unpublished. See Table 2.
%H A014417 Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, <a href="/A001950/a001950.pdf">Wythoff Wisdom</a>, unpublished, no date. [Cached copy, with permission]
%H A014417 Donald E. Knuth, <a href="http://dx.doi.org/10.1016/0893-9659(88)90176-0">Fibonacci multiplication</a>, Appl. Math. Lett., Vol. 1, No. 1 (1988), pp. 57-60.
%H A014417 Julien Leroy, Michel Rigo and Manon Stipulanti, <a href="http://dx.doi.org/10.1016/j.disc.2017.01.003">Counting the number of non-zero coefficients in rows of generalized Pascal triangles</a>, Discrete Mathematics, Vol. 340, No. 5 (2017), pp. 862-881.
%H A014417 Casey Mongoven, <a href="http://caseymongoven.com/b1087">Zeckendorf Representations no. 17</a> (a musical composition with A014417).
%H A014417 Wikipedia, <a href="https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem">Zeckendorf's theorem</a>.
%e A014417 The Zeckendorf expansions of 1, 2, ... are 1 = 1 = Fib_2 -> 1, 2 = 2 = Fib_3 -> 10, 3 = Fib_4 -> 100, 4 = 3+1 = Fib_4 + Fib_2 -> 101, 5 = 5 = Fib_5 -> 1000, 6 = 1+5 = Fib_2 + Fib_5 -> 1001, etc.
%p A014417 A014417 := proc(n)
%p A014417     local nshi,Z,i ;
%p A014417     if n <= 1 then
%p A014417         return n;
%p A014417     end if;
%p A014417     nshi := n ;
%p A014417     Z := [] ;
%p A014417     for i from A130234(n) to 2 by -1 do
%p A014417         if nshi >= A000045(i) and nshi > 0 then
%p A014417             Z := [1,op(Z)] ;
%p A014417             nshi := nshi-A000045(i) ;
%p A014417         else
%p A014417             Z := [0,op(Z)] ;
%p A014417         end if;
%p A014417     end do:
%p A014417     add( op(i,Z)*10^(i-1),i=1..nops(Z)) ;
%p A014417 end proc: # _R. J. Mathar_, Jan 31 2015
%t A014417 fb[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-- ]; FromDigits[fr]]; Table[ fb[n], {n, 0, 30}] (* _Robert G. Wilson v_, May 15 2004 *)
%t A014417 r = Map[Fibonacci, Range[2, 12]]; Table[Total[FromDigits@ PadRight[{1}, Flatten@ #] &@ Reverse@ Position[r, #] & /@ Abs@ Differences@ NestWhileList[Function[k, k - SelectFirst[Reverse@ r, # < k &]], n + 1, # > 1 &]], {n, 0, 33}] (* _Michael De Vlieger_, Mar 27 2016, Version 10 *)
%t A014417 FromDigits/@Select[Tuples[{0,1},7],SequenceCount[#,{1,1}]==0&] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, Aug 14 2019 *)
%o A014417 (PARI) Zeckendorf(n)=my(k=0,v,m); while(fibonacci(k)<=n,k=k+1); m=k-1; v=vector(m-1); v[1]=1; n=n-fibonacci(k-1); while(n>0,k=0; while(fibonacci(k)<=n,k=k+1); v[m-k+2]=1; n=n-fibonacci(k-1)); v \\ _Ralf Stephan_
%o A014417 (PARI) Zeckendorf(n)= { local(k); a=0; while(n>0, k=0; while(fibonacci(k)<=n, k=k+1); a=a+10^(k-3); n=n-fibonacci(k-1); ); a }
%o A014417 { for (n=0, 10000, Zeckendorf(n); print(n," ",a); write("b014417.txt", n, " ", a) ) } \\ _Harry J. Smith_, Jan 17 2009
%o A014417 (Haskell)
%o A014417 a014417 0 = 0
%o A014417 a014417 n = foldl (\v z -> v * 10 + z) 0 $ a189920_row n
%o A014417 -- _Reinhard Zumkeller_, Mar 10 2013
%o A014417 (Python)
%o A014417 from sympy import fibonacci
%o A014417 def a(n):
%o A014417     k=0
%o A014417     x=0
%o A014417     while n>0:
%o A014417         k=0
%o A014417         while fibonacci(k)<=n: k+=1
%o A014417         x+=10**(k - 3)
%o A014417         n-=fibonacci(k - 1)
%o A014417     return x
%o A014417 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 07 2017, after PARI code by _Harry J. Smith_
%Y A014417 Cf. A000045, A003794, A007895, A035517, A130234, A215022, A215023, A215024, A215025.
%Y A014417 a(n) = A003714(n) converted to binary.
%Y A014417 Cf. also A005614, A189920, A104324, A213911.
%Y A014417 See A104326 for dual Zeckendorf representation of n.
%K A014417 nonn,easy,base,nice
%O A014417 0,3
%A A014417 _Olivier Gérard_
%E A014417 Comment layout fixed by _Daniel Forgues_, Dec 07 2009
%E A014417 Typo corrected by _Daniel Forgues_, Mar 25 2010
%E A014417 Definition expanded and Duchene et al. reference added by _N. J. A. Sloane_, Aug 07 2018
%E A014417 Name corrected by _Michel Dekking_, Nov 30 2020