0,3

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.]

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.

D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.

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.

Tony D. Noe and Harry J. Smith, Table of n, a(n) for n=0,...,10000

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.

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)

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

(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]

Cf. A000045, A003794, A007895, A035517.

a(n) = A003714(n) converted to binary.

Sequence in context: A107411 A019513 A037415 this_sequence A007924 A115794 A105424

Adjacent sequences: A014414 A014415 A014416 this_sequence A014418 A014419 A014420

nonn,easy,base,nice

Olivier Gerard (olivier.gerard(AT)gmail.com)

Added a PARI program to generate the sequence. [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Jan 17 2009]