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

F_n = F_{n-1} + F_{n-2}

Sometimes an additional 1 is stuck at the front of the Fibonacci number sequence, but when dealing with Zeckendorf decompositions we’ll deliberately avoid doing that. For more on why this is important, see my more theoretical article on recurrences and Zeckendorf decompositions. Here, though, I’ll focus more on giving you the background needed to calculate Zeckendorf decompositions in Python. To do so I’ll briefly discuss induction and greedy algorithms, and then walk through some Python code that gives the Zeckendorf decomposition of a positive integer.

Image courtesy of zhuwei06191973 via Pixabay

Induction and Greedy Algorithms

Let’s start by rereading the last thing I said in the introduction:

“walk through some Python code that gives the Zeckendorf…