Zeckendorf

Published on 19 January 2026 (Updated: 19 January 2026)

Welcome to the Zeckendorf page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

rzuckerm

Description

Edouard Zeckendorf was a Belgian amateur mathematician who proposed a Theorem that states that every non-negative integer (N) can be represented as a sum of distinct non-consecutive Fibonacci Numbers. In other words,

N = F_c₁ + F_c₂ + … + F_{c_n}

where:

F_k is the k th Fibonacci number
c_i ≥ 2
c_{i + 1} > c_i + 1

Each Fibonacci number (F_k) is the sum of the previous two Fibonacci numbers:

F₀ = 0
F₁ = 1
F₂ = F₁ + F₀ = 0 + 1 = 1
F₃ = F₂ + F₁ = 1 + 1 = 2
…
F_k = F_{k - 1} + F_{k - 2}

This relationship is the reason why non-consecutive Fibonacci numbers are used.

To find the Fibonacci numbers that add up to N:

Find all the Fibonacci numbers up to and including N, starting at F₂.
Going from largest to smallest, select each Fibonacci number such that the sum of this value plus all the prior selected values is less than or equal to N.

For example, for N = 67, these are the Fibonacci numbers up to 67:

1, 2, 3, 5, 8, 13, 21, 34, 55

Select the appropriate Fibonacci numbers:

Trial Sum	Fibonacci Number	Selected
0	55	✅
55	34
55	21
55	13
55	8	✅
63	5
63	3	✅
66	2
66	1	✅

Therefore, using the selected numbers, N can be represented as:

67 = 55 + 8 + 3 + 1

A possible optimization for this procedure would be to skip Fibonacci numbers that are consecutive to the last selected value and to terminate the loop as soon as the sum equals to N.

Requirements

Create a file called "Zeckendorf" using the naming convention appropriate for your language of choice.

Write a sample program that accepts a single non-negative integer from the command line and outputs a comma-separated list of Fibonacci numbers whose sum equals the specified value. For zero, output an empty list. If the command line argument is missing or not a non-negative integer, output the error message specified in the Testing section.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Zeckendorf. In order to keep things simple, we split up the testing as follows:

Zeckendorf Valid Tests
Zeckendorf Invalid Tests

Zeckendorf Valid Tests

Description	Input	Output
Zero	"0"	""
Small Fibonacci Value	"55"	"55"
Small Non-Fibonacci Value	"67"	"55, 8, 3, 1"
Large Fibonacci Value	"10946"	"10946"
Large Non-Fibonacci Value	"16383"	"10946, 4181, 987, 233, 34, 2"

Zeckendorf Invalid Tests

Description	Input
No Input
Empty Input	""
Negative Input	"-2"
Floating Point Input	"2.6"
Non-Numeric Input	"bad"

All of these tests should output the following:

Usage: please input a non-negative integer

Articles

There is 1 article:

Zeckendorf in Python