Previous post

A Zeckendorf table in Python

January 10, 2026 at 5:15 PM by Dr. Drang

After writing this morning’s post, I went down to Channahon for a walk along the I&M Canal towpath. On the drive there and back, I thought about redoing the project in Python instead of Mathematica. It seemed like a fairly easy problem, and it was.

Recall that the goal was to reproduce this table from a recent Numberphile video:

Zeckendorf table from Numberphile video

Instead of using someone else’s code for creating the Zeckendorf representation of an integer (examples of which are relatively easy to find), I decided to write my own using the greedy algorithm outlined by Tony Padilla in the video. Here’s the script:

python:
 1:  #!/usr/bin/env python3
 2:  
 3:  from collections import defaultdict
 4:  
 5:  def zeck(n):
 6:    'Return the Zeckendorf list of Fibonacci numbers for n.'
 7:  
 8:    # Greedily subtract Fibonacci numbers from n until zero.
 9:    z = []
10:    left = n
11:    for f in reversed(fibs):
12:      if (m := left - f) >= 0:
13:        left = m
14:        z.append(f)
15:    return z
16:  
17:  # Fibonacci numbers less than 100, excluding the initial 1.
18:  fibs = [1, 1]
19:  while (n := fibs[-2] + fibs[-1]) < 100:
20:    fibs.append(n)
21:  del fibs[0]
22:  
23:  # Build the table.
24:  ztable = defaultdict(list)
25:  for i in range(1, 101):
26:    for z in zeck(i):
27:      ztable[z].append(i)
28:  
29:  # Print it.
30:  for f in fibs:
31:    print(', '.join(str(n) for n in ztable[f]))
32:    print()

The greedy algorithm is in the zeck function on Lines 5–15. It assumes the existence of a list of Fibonacci numbers saved in the global variable fibs. It goes through fibs in reverse order. If the current Fibonacci number can be subtracted from the number without going below zero, it is, and it’s also appended to the Zeckendorf representation list. This process is repeated, subtracting—if possible—each Fibonacci number in turn from the remaining difference until we get to the end of the reversed fibs list.

Unlike the ZeckendorfRepresentation function in the Wolfram Language, zeck doesn’t return a list of ones and zeros whose positions are associated with Fibonacci numbers; it returns the Fibonacci numbers themselves. So zeck(50) returns [34, 13, 3].

You probably see some things in zeck that could be made more efficient. Me too. But in a small problem like this, I didn’t think those efficiencies were worth the effort.

Also note that zeck is not a general-purpose function. I wrote it specifically for this script, and it’s built on certain assumptions. The assumptions have to do with how it’s called and how the global fibs list is constructed:

  1. The argument passed to zeck is a number small enough that its Zeckendorf representation consists entirely of numbers from the fibs list.
  2. The fibs list is in increasing order.
  3. The fibs list does not contain the initial one of the Fibonacci sequence.

Lines 17–21 create the fibs list to meet these conditions. After the deletion on Line 21, it’s

[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

My favorite part of this bit of code is the walrus operator (:=) in Line 19. Apparently, there are people who don’t like the walrus operator. Don’t listen to them.

Lines 23–27 then build the table. In this case, I used a defaultdict called ztable whose keys are the Fibonacci numbers and whose values are the lists of numbers that have that key in their Zeckendorf representation.

Finally, Lines 29–32 print out the values of ztable. Here they are, formatted to fit better in this space:

1, 4, 6, 9, 12, 14, 17, 19, 22, 25, 27, 30, 33, 35,
38, 40, 43, 46, 48, 51, 53, 56, 59, 61, 64, 67, 69,
72, 74, 77, 80, 82, 85, 88, 90, 93, 95, 98

2, 7, 10, 15, 20, 23, 28, 31, 36, 41, 44, 49, 54,
57, 62, 65, 70, 75, 78, 83, 86, 91, 96, 99

3, 4, 11, 12, 16, 17, 24, 25, 32, 33, 37, 38, 45,
46, 50, 51, 58, 59, 66, 67, 71, 72, 79, 80, 87, 88,
92, 93, 100

5, 6, 7, 18, 19, 20, 26, 27, 28, 39, 40, 41, 52, 53,
54, 60, 61, 62, 73, 74, 75, 81, 82, 83, 94, 95, 96

8, 9, 10, 11, 12, 29, 30, 31, 32, 33, 42, 43, 44,
45, 46, 63, 64, 65, 66, 67, 84, 85, 86, 87, 88, 97,
98, 99, 100

13, 14, 15, 16, 17, 18, 19, 20, 47, 48, 49, 50, 51,
52, 53, 54, 68, 69, 70, 71, 72, 73, 74, 75

21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88

34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 49, 50, 51, 52, 53, 54

55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67,
68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88

89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

This matches both the video screenshot above and the list given in this morning’s post.

Previous post