Programming Praxis

The folks at /r/dailyprogrammer publish programming exercises on a regular basis; you might want to have a look. They frequently steal my exercises, so today I will steal one of theirs.

Any positive integer can be represented as the sum of one or more non-consecutive fibonacci numbers. For instance, 100 = 2 + 8 + 89. Note that 100 can also be written using fibonacci sums as 89 + 8 + 2 + 1 or 55 + 34 + 8 + 3, but those use consecutive fibonacci numbers (2 + 1 for the first representation, 55 + 34 for the second). Belgian mathematician Edouard Zeckendorf proved that such a representation is unique.

Zeckendorf representations can easily be found by a greedy strategy. Start with the largest fibonacci number less than the target number. Then choose the largest fibonacci number less than the remainder after subtracting the first number. And so on, stopping when the remainder is a fibonacci number itself.

Your task is to write a function that finds the Zeckendorf representation of a positive integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2