Zeckendorf Decompositions in Python

Introduction: what are Zeckendorf Decompositions?

In this article I’m going to talk about Zeckendorf Decompositions and how to manipulate and construct these sums in Python. Of course, I should probably start by defining what these mysterious sums are. A Zeckendorf decomposition is a way of writing a positive integer as a sum of non-consecutive Fibonacci numbers. For clarify, the Fibonacci numbers are the sequence

1, 2, 3, 5, 8, 13, …

defined with the recursive relation