Base Fibonacci
I read a blog post titled The golden ratio as a number base. It had an interesting statement:
According to Zeckendorf’s Theorem, every positive integer can be represented in a unique way as a sum of distinct, non-consecutive Fibonacci numbers.
Edit 2026-10-01: Numberphile on YouTube did a video on Base Fibonacci, but I scooped them by almost 2 months! The mathematician explaining Zeckendorf’s theorem to Brady Haran, Tony Padilla, does a great job of motivating, almost proving, the theorem.
This is true.
Try it right here. Enter a number less than or equal to 1836311903,
click Convert.
Through the magic of math and computer programming,
you should see the Fibonacci number(s) that sum to your number
in the output field.
Fibonacci Numbers as a base
One consequence of Zeckendorf’s Theorem is that you can use Fibonacci Numbers as a “base” for a numeral system.
There’s a system called Fibonacci Encoding that embodies a “base Fibonacci” in a clever way. It does have the drawback that you can’t represent 0 (zero). It looks a bit like some kind of binary representation, but it’s not, and zero-characters (or bits) on the left of a numeral are significant.
To illustrate, the Zeckendorf representation of 101 is (89, 8, 3, 1) Fibonacci Encoding is different “endian” than the usual base 10 number, the least significant digit is on the left. There’s an extra ‘1’ at the right as well.
The Fibonacci Sequence of numbers less than or equal to 101 is: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. There are ten elements in the part of the Fibonacci Sequence lass than 101. That means there will be ten digits in the Fibonacci Encoding of 101. There will be a ‘1’ digit for the values of the Zeckendorf Representation of 101, a 0 digit for each element of the subsequence that’s not in 101’s Zeckendorf Representation.
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
Based on the above, the Fibonacci Encoding is 10101000011.
There’s an extra ‘1’ at the right hand side so you can concatenate Fibonacci Encodings and still figure out where the end of one number is. According to Zeckendorf’s Theorem, the Fibonacci numbers summing to some given number are non-consecutive.
The extra trailing ‘1’ allows you to distinguish the end of an encoded number. Here’s Fibonacci Encodings of 65 and 101 concatenated:
010010001110101000011
Reading left-to-right, the two encodings break after the second consecutive ‘1’.
The “two consecutive 1s” gives a stream of Fibonacci Encoded numbers a property like that of a stream of UTF-8 encoded characters. If something changes a ‘1’ to a ‘0’, a ‘0’ to a ‘1’, or deletes a character in a stream of Fibonacci Encoded numbers, a process reading that stream can re-synchronize at the next occurrence of two consecutive ‘1’ characters.
Fibonacci Encoding has none of the benefits of a positional notation system. Odd numbers can have a 1 or a 0 as the initial (least significant) digit, so you can’t use that digit for an odd/even test.
There’s nothing like the base 10 representation of multiples of 5 having a ‘5’ or ‘0’ as the least significant digit, or if the sum of a number’s digits equal a multiple of 9, the entire number is a multiple of 9. None of the useful tricks apply to Fibonacci Encoded numbers.
The ‘1’ digits don’t progress logically as you count up. You can’t add two Fibonacci-encoded-numbers as one typically adds positional notation numbers.
| Base 10 | Fibonacci Encoding |
|---|---|
| 99 | 01001000011 |
| 100 | 00101000011 |
| 101 | 10101000011 |
| 102 | 00000100011 |
Look how the least significant (left-most) digits jump around between the Fibonacci Encodings of 100, 101 and 102. Baffling.
Of course I have a code repo for Golang code that does this as well.
Over the years, I’ve come to the conclusion that I don’t understand a topic unless I’ve done something with it: made a gadget that embodies a principle, or simulated it, or done an experiment.
Zeckendorf’s theorem was no different. As theorems go, it wasn’t unusually subtle, writing the programs didn’t cause any light bulb moments. But I did get confidence in it by trying it repeatedly. I didn’t put in a lot of checks on indexes into arrays staying non-negative in my code. and not indexing off the small-value end of other arrays. I relied on the “non-consecutive” part of the theorem, and trusting that a selection of Fibonacci numbers can sum to any integer.
With respect to writing programs, I did have some difficulty getting Zeckendorf Representations correct. My first cut was extra clumsy. What you see in the repo is due to plowing through stupidly, sleeping on it, re-writing to be somewhat more subtle, then writing JavaScript versions that appear in this web page. I farmed some improvements back from JavaScript to Go versions, but I wouldn’t have written the same JavaScript without having written the Go first.