6 kyu

Zeckendorf representation

193 of 276zieglerk

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.

Fundamentals

More By Author:

Check out these other kata created by zieglerk

Stats:

CreatedMay 19, 2015
PublishedJul 5, 2015
Warriors Trained866
Total Skips66
Total Code Submissions1180
Total Times Completed276
Python Completions193
JavaScript Completions63
Haskell Completions19
Ruby Completions25
Total Stars20
% of votes with a positive feedback rating95% of 86
Total "Very Satisfied" Votes78
Total "Somewhat Satisfied" Votes7
Total "Not Satisfied" Votes1
Total Rank Assessments18
Average Assessed Rank
6 kyu
Highest Assessed Rank
6 kyu
Lowest Assessed Rank
8 kyu
Ad
Contributors
  • zieglerk Avatar
  • anter69 Avatar
  • JohanWiltink Avatar
  • user9644768 Avatar
  • ᛚᚨᚱᛊ ᚺᛖᚾᚱᛁᚲ Avatar
Ad