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 decomposition of a positive integer”

I want to emphasize the word “the” in the above line. That’s because it turns out there is one, and only one, Zeckendorf decomposition. In other words, every positive integer has a unique Zeckendorf decomposition! This is a theorem proven back in the 1970s, and the use of only one 1 in the Fibonacci sequence is extremely important to make this work out. It’s important to understand some of the basic tools embedded in the proof, because they are important motivators for the code in the upcoming section of this article.

The two tools, of course, are induction and greedy algorithms.

Induction is a proof technique often used to prove that a statement is true for all natural numbers n. Let’s state Zeckendorf’s Theorem this way:

For any natural number n, there exists a unique Zeckendorf decomposition of n.

The procedure of induction works as follows: we first prove the statement for a base case, or a small value of n, from which the proof for all other values of n will follow. Typically the base case is n = 1, because that is almost always easy to prove. Then, the heart of the proof is in what’s called the inductive step: you assume the claim you wish to prove is true for a value of n that is not named explicitly. Using that, you prove the original claim for n + 1. This is precisely how Zeckendorf’s Theorem was proven, along with many other results in number theory, combinatorics, graph theory, and analysis. If you study mathematics at the university level you will probably see this proof technique many times.

Now I’m going to briefly touch on the concept of a greedy algorithm. A greedy algorithm is a procedure in which you construct a mathematical object by identifying the largest pieces first. Now, the meaning of “largest piece” varies wildly based on the context, but our focus here is on sums of positive integers. In other words, Zeckendorf decompositions are constructed by first identifying the largest Fibonacci numbers in the decomposition, and then working our way down to the smaller ones. This is how the proof of Zeckendorf’s theorem goes about. It’s also the principle on which we will write a program to construct Zeckendorf decompositions. Let’s move onto that, but here’s the Wikipedia page for greedy algorithms if you wish to read more on that.

How to find the Zeckendorf Decomposition using Python

Now we get into the heart of the article, coding up an algorithm for finding Zeckendorf decompositions. I wrote the program using a greedy algorithm and will go through it step by step to explain how the code works. More observant readers may notice there are a few spots where I compromised efficiency, and I did that for sake of clarity of my thought process. Now, here’s the complete program. The input is a natural number n, and the output is the Zeckendorf decomposition for n (which we already know exists and is unique).

The means of accomplishing our task in Python has two main steps. The first step is to create a list of all Fibonacci numbers less than n. Essentially, we are generating the “pool” of possible Fibonacci numbers that could be in the Zeckendorf decomposition for n. Since a Zeckendorf decomposition only contains positive integers, none of the Fibonacci numbers we use can be larger than n.

The second step is to actually build the Zeckendorf decomposition. We use the list created in the first part of the algorithm to iterate through all the possible Fibonacci numbers for our decomposition, from largest to smallest, just as the greedy algorithm proof of Zeckendorf’s theorem suggests.

Now for a more detailed breakdown of the code I wrote.

These first few lines feature base cases and act as a failsafe so that the loops that run later don’t raise index errors. The assertion is just a sanity check, because only positive integers should be inputted, and if n were to equal 1, 2, or 3, the code would have terminated before reaching the assertion.

Since we are now assuming n ≥ 4, we know that we need the Fibonacci numbers 1, 2, and 3 as possible candidates to include in the Zeckendorf decomposition (for instance, if n = 4, the decomposition is 3+1). The variable fibCounter is a means of tracking the largest Fibonacci number in the list listOfFibs as we add more numbers to the list.

The purpose of the while loop that follows is to finish adding Fibonacci numbers to listOfFibs we may need. The while statement is fibCounter < n because we don’t want to include any Fibonacci numbers bigger than n. Since the Fibonacci numbers are constructed recursively with the recursive formula

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

we can figure out the next number to add to listOfFibs by using this recursion over and over. Update the value of fibCounter accordingly, and then add this number to listOfFibs at the end of the list, to ensure the Fibonacci numbers are listed from smallest to largest. All things considered, the Fibonacci numbers can be written from largest to smallest, but writing the code the way I did is slightly more concise.

Once the value of fibCounter reaches or exceeds n — which will happen after finitely many iterations of the while loop since secondToLast will always be positive — we exit the while loop. If the value of fibCounter is strictly bigger than n, we need to make a small “correction” to our list. The list listOfFibs will include one Fibonacci number larger than n, so we look to remove it before beginning the construction of the Zeckendorf decomposition.

These lines of code are setup for building the Zeckendorf decomposition. The variable numberOfFibs tells us how many Fibonacci numbers are in listOfFibs, and zeckDecomp is the string which will gradually be transformed into the Zeckendorf decomposition (the output of this function is a string). The variable index will serve as a tracker for identifying how far along we are in iterating over all the numbers in listOfFibs, and the remaining variable tells us how much of our original number n still needs to be decomposed into Fibonacci numbers. We initiate the value of remaining to n and it will decrease over time. Finally, we start the Zeckendorf decomposition with the last number in listOfFibs. This will always be the largest Fibonacci number that is less than (or equal to) n.

After adding this Fibonacci number to the string that we will eventually output, we subtract the value of that Fibonacci number from the remaining variable. That tells us the new, smaller number we still need to decompose. We also subtract 2 from the value of index, because we cannot use consecutive Fibonacci numbers in a Zeckendorf decomposition (remember the definition?). If the last two lines were to be inverted, we would be subtracting the wrong Fibonacci number from the value of remaining, and this produces a bug, so be careful!

At long last, the construction of the Zeckendorf decomposition. The goal is to get the value of remaining to 0, because that means we’ve completely decomposed n, into a sum of Fibonacci numbers that equals n. In each iteration of the loop, we look at a Fibonacci number in listOfFibs depending on the value of index. If that Fibonacci number is less than the value of remaining, we append it to the end of the zeckDecomp string, and subtract that Fibonacci number from the value of remaining. In this case we subtract 2 from index, because again, we can’t use consecutive Fibonacci numbers in a Zeckendorf decomposition.

If the Fibonacci number we landed on is greater than the value of remaining, we skip that Fibonacci number, and lower the value of index by 1. This means we just check the next largest Fibonacci number. Since the value of index decreases by at least 1 in every iteration of the while loop, this loop will eventually terminate. When it does, we return the string zeckDecomp, and we’re done!

Based on how we wrote this code, the string zeckDecomp will have the needed Fibonacci numbers listed from largest to smallest. Since addition is commutative, there’s no reason why we can’t list them from smallest to largest. I think listing them largest to smallest just better illuminates the underlying idea behind this code, which is a greedy algorithm hard at work.

As a side note, I contributed to two published papers dealing with Zeckendorf decompositions and studying some relevant questions in probability. They are linked here and here.

Math PhD Student University of Tennessee | Academic Sales Engineer | Writer, Educator, Researcher

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store