|
| |
|
|
A014417
|
|
Representation of n in base of Fibonacci numbers.
|
|
64
|
|
|
|
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
|
|
|
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
|
|
|
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 (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, 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
|
Added a PARI program to generate the sequence. [From Harry J. Smith, Jan 17 2009]
Comment layout fixed by Daniel Forgues, Dec 07 2009
Typo corrected by Daniel Forgues, Mar 25 2010
|
|
|
STATUS
|
approved
|
| |
|
|
