login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 one-dimensional 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. Addison-Wesley, Reading, MA, 1990.

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

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, 179-182, 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=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 */

(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) ) } /* 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 21 16:47 EDT 2014. Contains 248377 sequences.