|
|
A035516
|
|
Triangular array formed from Zeckendorf expansion of integers: repeatedly subtract the largest Fibonacci number you can until nothing remains.
|
|
15
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
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
|
|
|
EXAMPLE
|
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
|
|
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 *)
|
|
PROG
|
(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'
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|