%I A014417
%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
%N A014417 Representation of n in base of Fibonacci numbers.
%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.]
%D A014417 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 1990.
%D A014417 D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.
%D A014417 Zeckendorf, E., Representation des nombres naturels par une somme des 
               nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. 
               Liege 41, 179-182, 1972.
%H A014417 Tony D. Noe and Harry J. Smith, <a href="b014417.txt">Table of n, a(n) 
               for n=0,...,10000</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.
%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}] (from Robert G. Wilson v May 15 2004)
%o A014417 (PARI) Zeckendorf(n)=local(k,v,m):k=0: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 
               (from R. 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 } { for (n=0, 10000, 
               Zeckendorf(n); print(n," ",a); write("b014417.txt", n, " ", a) ) 
               } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Jan 17 2009]
%Y A014417 Cf. A000045, A003794, A007895, A035517.
%Y A014417 a(n) = A003714(n) converted to binary.
%Y A014417 Sequence in context: A107411 A019513 A037415 this_sequence A007924 A115794 
               A105424
%Y A014417 Adjacent sequences: A014414 A014415 A014416 this_sequence A014418 A014419 
               A014420
%K A014417 nonn,easy,base,nice
%O A014417 0,3
%A A014417 Olivier Gerard (olivier.gerard(AT)gmail.com)
%E A014417 Added a PARI program to generate the sequence. [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), 
               Jan 17 2009]