

A014417


Representation of n in base of Fibonacci numbers.


69



0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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.
"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.]
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
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
Also, numbers, written in binary, such that no adjacent bits are equal to 1: A onedimensional analog of the matrices considered in A228277/A228285, A228390, A228476, A228506 etc.  M. F. Hasler, Apr 27 2014


REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990.
D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 5760.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
E. Zeckendorf, Representation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liege 41, 179182, 1972.


LINKS

T. D. Noe and Harry J. Smith, Table of n, a(n) for n = 0..10000
Casey Mongoven, Zeckendorf Representations no. 17 (a musical composition with A014417)


EXAMPLE

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.


MATHEMATICA

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


PROG

(PARI) Zeckendorf(n)=local(k, v, m):k=0:while(fibonacci(k)<=n, k=k+1):m=k1:v=vector(m1):v[1]=1:n=nfibonacci(k1): while(n>0, k=0: while(fibonacci(k)<=n, k=k+1): v[mk+2]=1:n=nfibonacci(k1)):v /* Ralf Stephan */
(PARI) Zeckendorf(n)= { local(k); a=0; while(n>0, k=0; while(fibonacci(k)<=n, k=k+1); a=a+10^(k3); n=nfibonacci(k1); ); a } { for (n=0, 10000, Zeckendorf(n); print(n, " ", a); write("b014417.txt", n, " ", a) ) } /* Harry J. Smith, Jan 17 2009 */
(Haskell)
a014417 0 = 0
a014417 n = foldl (\v z > v * 10 + z) 0 $ a189920_row n
 Reinhard Zumkeller, Mar 10 2013


CROSSREFS

Cf. A000045, A003794, A007895, A035517, A215022, A215023, A215024, A215025.
a(n) = A003714(n) converted to binary.
Cf. A189920, A104324, A213911.
Sequence in context: A019513 A037415 A123001 * A211027 A185101 A007924
Adjacent sequences: A014414 A014415 A014416 * A014418 A014419 A014420


KEYWORD

nonn,easy,base,nice


AUTHOR

Olivier Gérard


EXTENSIONS

Comment layout fixed by Daniel Forgues, Dec 07 2009
Typo corrected by Daniel Forgues, Mar 25 2010


STATUS

approved



