The Fibonacci Number Base

In a blog post of Sunday, 15th November 2015, titled Goldbach's Conjecture and Zeckendorf's Theorem, I wrote the following:

I came across Zeckendorf's Theorem when examining the number 24331. It's similar to Goldbach's Conjecture in that it deals with the decomposition of numbers but into Fibonacci numbers, not primes. It states, to quote from Wikipedia again, that: 

Every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. 

Now the first few Fibonacci numbers are: 

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 

The Wikipedia article goes on to state that the theorem has two parts: 

Existence: every positive integer n has a Zeckendorf representation.Uniqueness: no positive integer n has two different Zeckendorf representations. 

The example is given of the number 100 = 89 + 8 + 3. There are other ways of representing 100 as the sum of Fibonacci numbers: 100 = 89 + 8 + 2 + 1 and 100 = 55 + 34 + 8 + 3 but these are not Zeckendorf representations because 1 and 2 are consecutive Fibonacci numbers, as are 34 and 55.

This is the first time I've revisited the topic. I found a site that will calculate the relevant Fibonacci numbers that add to a given number. Figure 1 shows the calculation for today's number of 25684:

Figure 1: source

The result as can be seen is {1,21,55,144,987,6765,17711}. I've also developed an algorithm in SageMath that does this also but I'm still refining it. The Zeckendorf system uses the set with the fewest Fibonacci numbers in it. The same site has a calculator that will express a given number in terms of a Fibonnaci number base using the digits 0 and 1. The idea is that a number like 25684 would be represented as 101000100010101000001 where the rightmost 1 stands for the largest Fibonacci number and the leftmost 1 or 0 stands for the smallest Fibonacci number (which is 1 in this system). If a particular number does not form part of the same then its position is occupied by a 0. The calculator is shown in Figure 2:

Figure 2: source

My SageMath algorithm clumps all the 0's and 1's together and I'm still trying to work out what the problem is. For numbers in the vicinity of my current age (in days), seven or eight numbers seem to be generally required:

• \(25684 = 101000100010101000001_{Zeck}\) with 7 ones 
• \(25685 = 101000100010101000010_{Zeck}\) with 7 ones
• \(25686 = 101000100010101000100_{Zeck}\) with 7 ones
• \(25687 = 101000100010101000101_{Zeck}\) with 8 ones
• \(25688 = 101000100010101001000_{Zeck}\) with 7 ones
• \(25689 = 101000100010101001001_{Zeck}\) with 8 ones

As a number base, it's hardly compact but a simple way to compress it would be to use the same system that it used in data compression: representing consecutive runs of 0's and 1's by the binary digit and an associated superscript that expresses the length of the run. In this way, the numbers above become:

• \(25684 = 1010^310^3101010^51_{Zeck}\) 
• \(25685 =1010^310^3101010^410_{Zeck}\)
• \(25686 =1010^310^3101010^310^2_{Zeck}\)
• \(25687 = 1010^310^3101010^3101_{Zeck}\)
• \(25688 = 1010^310^3101010^210^3_{Zeck}\)
• \(25689 = 1010^310^3101010^210^21_{Zeck}\)

It's interesting to note, using the calculator in Figure 1, how many possible sets of Fibonacci numbers there are that add to a given number. Here are the results for the previous numbers:

• 66 sets with a sum of 25684
• 66 sets with a sum of 25685
• 103 sets with a sum of 25686
• 37 sets with a sum of 25687
• 74 sets with a sum of 25688
• 74 sets with a sum of 25689

The minimal set of numbers is being used to determine the Zeckendorf representation but others configurations are possible. As the site says:

The Zeckendorf system uses the set with the fewest Fibonacci numbers in it. What about choosing that set with the most Fibonacci numbers with a sum of n, each Fibonacci number being used at most once? This is called the maximal Fibonacci bit representation. "Bit" means that the only digits in the representations are 0 and 1. Zeckendorf's is therefore the minimal Fibonacci bit representation.

For 25684, the maximal set is 

{1, 3, 5, 13, 21, 34, 55, 89, 144, 233, 610, 987, 1597, 4181, 6765, 10946}

This consists of 16 numbers and can be found using the calculator in Figure 1. Compare this with the full set of Fibonacci numbers:

{1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946}

This number would thus become \(11101110111111111101\) or \(1^301^301^{10}01\) used my superscript system described earlier. As can be seen, only three numbers are missing and thus there are only three 0's. In order to avoid confusion, the subscript MaxFib or the like should be e.g. \(25684 = 11101110111111111101_{MaxFib}\) or \(1^301^301^{10}01_{MaxFib}\). Here's some historical background:

This system is also called the Zeckendorf representation of a number after Edouard Zeckendorf who wrote about it (in French) in 1972. He proved that each representation of a number n as a sum of distinct Fibonacci numbers, but where no two consecutive Fibonacci numbers are used (and there is only one column headed "1"), is unique. However, earlier, Lekkerkerker had written about this representation in 1952 in Dutch showing that there is only one way to write a number in this system but, unfortunately for him, the system is now generally called Zeckendorf's.

In formal mathematical terms, the Zeckendorf representation can be defined as follows:

A number written as a sum of nonconsecutive Fibonacci numbers, such that$$n=\sum_{k=0}^L \epsilon_k \,F_k$$where \(\epsilon_k\) are 0 or 1 and \( \epsilon_k \times \epsilon_{k+1}=0\). Every positive integer can be written uniquely in such a form (which is in itself a particular example of a Ostrowski numeration).

Here is a link to a PDF file of an academic paper with the following abstract:

Three contrasting polyphonic musical compositions based on Zeckendorf representations in the style of music characterised by Fibonacci numbers and the golden ratio are presented and analysed.