A035516 Triangular array formed from Zeckendorf expansion of integers: repeatedly subtract the largest Fibonacci number you can until nothing remains.
0, 1, 2, 3, 3, 1, 5, 5, 1, 5, 2, 8, 8, 1, 8, 2, 8, 3, 8, 3, 1, 13, 13, 1, 13, 2, 13, 3, 13, 3, 1, 13, 5, 13, 5, 1, 13, 5, 2, 21, 21, 1, 21, 2, 21, 3, 21, 3, 1, 21, 5, 21, 5, 1, 21, 5, 2, 21, 8, 21, 8, 1, 21, 8, 2, 21, 8, 3, 21, 8, 3, 1, 34, 34, 1, 34, 2, 34, 3, 34, 3, 1, 34, 5, 34, 5, 1, 34, 5, 2
Offset: 0
Examples
16 = 13 + 3, so row 16 is 13, 3. [Corrected by _Sean A. Irvine_, Oct 14 2020]
The first few rows are:
0;
1;
2;
3;
3, 1;
5;
5, 1;
5, 2;
8;
8, 1;
8, 2;
...
Row 1000000 is 832040,121393,46368,144,55. Indeed, the Maple program yields in no time Z(1000000) = {55,144,46368,121393,832040}. - _Emeric Deutsch_, Oct 22 2014
References
- Zeckendorf, E., Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.
Links
- T. D. Noe, Rows n=0..1000 of triangle, flattened
- N. J. A. Sloane, Classic Sequences
Programs
-
Haskell
a035516 n k = a035516_tabf !! n !! k a035516_tabf = map a035516_row [0..] a035516_row 0 = [0] a035516_row n = z n $ reverse $ takeWhile (<= n) a000045_list where z 0 _ = [] z x (f:fs'@(_:fs)) = if f <= x then f : z (x - f) fs else z x fs' -- Reinhard Zumkeller, Mar 10 2013
-
Maple
with(combinat): Z := proc (n) local F, LF, A, m: F := proc (n) options operator, arrow: fibonacci(n) end proc: LF := proc (m) local i: for i from 0 while F(i) <= m do end do: F(i-1) end proc: A := {}: m := n: while 0 < m do A := `union`(A, {LF(m)}): m := m-LF(m) end do: A end proc: # The Maple program, with the command Z(n), yields the set of the Fibonacci numbers in the Zeckendorf representation of n (terms in {} are in reverse order). - Emeric Deutsch, Oct 21 2014 -
Mathematica
t = Fibonacci /@ Range@ 12; Table[If[MemberQ[t, n], {n}, Most@ MapAt[# + 1 &, Abs@ Differences@ FixedPointList[# - First@ Reverse@ TakeWhile[t, Function[k, # >= k]] &, n], -1]], {n, 41}] // Flatten (* faster, or *) t = Fibonacci /@ Range@ 12; {{0}}~Join~Table[First@ Select[ Select[ IntegerPartitions@ n, Times @@ Boole@ Map[MemberQ[t, #] &, #] == 1 &], Times @@ Boole@ Map[# > 1 &, Abs@ Differences@ Map[Position[t, #][[1, 1]] &, #, {1}]] == 1 &], {n, 41}] // Flatten (* Michael De Vlieger, May 17 2016 *)
Extensions
More terms from James Sellers, Dec 13 1999
Comments