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.

T. D. Noe, Table of n, a(n) for n=0..1000

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)

Cf. A000045, A003794, A007895, A035517.

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

Adjacent sequences: A014414 A014415 A014416 this_sequence A014418 A014419 A014420

Sequence in context: A107411 A019513 A037415 this_sequence A007924 A115794 A105424

nonn,easy,base,nice

Olivier Gerard (ogerard(AT)ext.jussieu.fr)