Zeckendorf representation
Description:
Every positive integer can be written as a sum of Fibonacci numbers. For example 10 = 8 + 2
or 5 + 3 + 2
or 3 + 3 + 2 + 2
. Apparently, this representation is not unique.
It becomes unique, if we rule out consecutive Fibonacci numbers: this is Zeckendorf's theorem, first proven by Lekkerkerker in 1952. In the example above, this excludes the last two representations (containing the consecutive Fibonacci numbers 2
and 3
), and we are left with the Zeckendorf representation 10 = 8 + 2
.
Complete the function that returns the Zeckendorf representation of a given integer n
as a list of Fibonacci numbers in decreasing order. Return an empty list for n = 0
and None/nil
for negative n
.
Hint: Be greedy!
Footnote: The Zeckendorf representation is closely connected to the Fibonacci coding.
Similar Kata:
Stats:
Created | May 19, 2015 |
Published | Jul 5, 2015 |
Warriors Trained | 866 |
Total Skips | 66 |
Total Code Submissions | 1180 |
Total Times Completed | 276 |
Python Completions | 193 |
JavaScript Completions | 63 |
Haskell Completions | 19 |
Ruby Completions | 25 |
Total Stars | 20 |
% of votes with a positive feedback rating | 95% of 86 |
Total "Very Satisfied" Votes | 78 |
Total "Somewhat Satisfied" Votes | 7 |
Total "Not Satisfied" Votes | 1 |
Total Rank Assessments | 18 |
Average Assessed Rank | 6 kyu |
Highest Assessed Rank | 6 kyu |
Lowest Assessed Rank | 8 kyu |