Zeckendorf's theorem

The first 88 natural numbers in Zeckendorf representation.
The width of a rectangle is a Fibonacci number (and its height). Rectangles of the same color are congruent. The vertical stripes have a width of 10. ${\displaystyle f_{i}}$ ${\displaystyle f_{i-1}}$

The Zeckendorf Theorem (also: Zeckendorf Theorem) named after Edouard Zeckendorf states that every natural number can be written uniquely as the sum of different, not directly consecutive Fibonacci numbers with indices . That is, there is a unique representation of the shape for each ${\displaystyle n>0}$ ${\displaystyle f_{i}}$ ${\displaystyle i\geq 2}$ ${\displaystyle n\in \mathbb {N} }$

${\displaystyle n=\sum _{i=2}^{k}c_{i}f_{i}}$

with and for everyone . The resulting sequence of zeros and ones is called the Zeckendorf sequence (also: Zeckendorf representation). ${\displaystyle c_{i}\in \{0,1\}}$ ${\displaystyle c_{i}c_{i+1}=0}$ ${\displaystyle i}$ ${\displaystyle \left(c_{i}\right)_{i\in 1+\mathbb {N} }}$

Historical note

While the theorem is (eponymically) named after Zeckendorf, an author who published it in 1972 , exactly this result was published 20 years earlier by Gerrit Lekkerkerker . Accordingly, Zeckendorf's theorem is once again an example of Stigler's law of eponyms .

Derivation

In the graphic, the 45 ° inclined diagonal is a stepped step down to the right. The integer grid is down as ordinate , to the right as abscissa construed. The following findings can be derived:

1. Every natural number appears as an ordinate - and thus also as an abscissa.
2. The layer of thickness 1 specified by an ordinate is divided from left to right into (horizontal) segments of strictly decreasing width, each width a Fibonacci number.

These properties clearly apply to the induction start of width = height = ${\displaystyle 1}$ . It is assumed that the representation for all triangles (all are isosceles and right-angled ) up to and including the abscissa = ordinate = is ${\displaystyle f_{n}\!\!-\!\!1}$ clearly possible (induction assumption). For this purpose, below a rectangle of the format   width = height = ${\displaystyle f_{n}\;\times }$ ${\displaystyle f_{n-1}}$   added to which the right-flush with the base side of a triangle format width = height = ${\displaystyle f_{n-1}\!\!-\!\!1}$ is added. The additions have the total width. Together with the triangle of the induction hypothesis, a triangle of height = (induction step) results . ${\displaystyle f_{n}+(f_{n-1}\!\!-\!\!1)=f_{n+1}\!\!-\!\!1.}$ ${\displaystyle (f_{n}\!\!-\!\!1)+f_{n-1}=f_{n+1}\!\!-\!\!1}$

The two statements made above still apply to the appendices. From the first follows the existence of the Zeckendorf representation.

From the second it follows that the widths of the segments that lie on the right of a large rectangle are Fibonacci numbers and are always smaller than the height of the rectangle - with the result that there are no two summands in the Zeckendorf representation that appear as Fibonacci -Numbers are adjacent to each other.

Since a Fibonacci number may appear a maximum of once in the Zeckendorf representation and cannot be replaced by the sum of individual Fibonacci numbers that are smaller by more than one index, the representation is clear.

Fibonacci code

Since consecutive Fibonacci numbers are excluded in the Zeckendorf sequence, no two ones in a Zeckendorf sequence can be directly behind one another. The Fibonacci code is created from the Zeckendorf sequence, which 1ends on the right with a most significant one ( ), by adding another 1(no place value ). The double one 11plays the role of the comma , which separates the code words (consisting of natural numbers) in a variable length coding.

The Fibonacci code is in direct competition with the binary coded ternary comma code, in which a “trit” is represented by two bits ( 00=: 0, 10=: 1 and 01=: 2) and the double ones play 11the role of the comma. Assuming a geometric distribution of the natural numbers , the Fibonacci code is ${\displaystyle 1/n^{q}}$ ${\displaystyle n\in \mathbb {N} }$

${\displaystyle q_{\mathrm {fib} }=\log _{\Phi }(2)=1/\log _{2}(\Phi )\approx 1{,}440}$

(with as the golden ratio ) and with the ternary comma code ${\displaystyle \Phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618}$

${\displaystyle q_{\mathrm {tek} }=\log _{3}(4)\approx 1{,}262}$ .

The latter is asymptotically somewhat shorter, but somewhat longer for the very small and mostly more frequent numbers.

For small natural numbers , the two codes are compared in the table, each with an indication of their length in bits. From this length is a calculated probability distribution , the so-called. Implied (Engl. Implied probability distribution ) , for which the code is nearly optimal. Both codes start on the left with the least significant bit, so they are notated in little-endian . (In this article, the indexing of the Fibonacci code starts with 1, whereas the ternary code should start with the index (and exponent) 0, as is usual in place value systems. The Fibonacci numbers we are talking about start with so that the Fibonacci number in the Zeckendorf sequence corresponds to the leftmost digit (at index 1).) ${\displaystyle n}$ ${\displaystyle l(n)}$ ${\displaystyle p(n)=2^{-l(n)}}$ ${\displaystyle f_{2}=1,f_{3}=2,}$ ${\displaystyle f_{2}=1}$

${\displaystyle n}$	Zeckendorf representation		Fibonacci code	${\displaystyle l_{\mathrm {fib} }}$	ternary with a comma	${\displaystyle l_{\mathrm {tek} }}$
1	= 1	= ${\displaystyle f_{1+1}}$	11	2	1011	4th
2	= 2	= ${\displaystyle f_{1+2}}$	011	3	0111	4th
3	= 3	= ${\displaystyle f_{1+3}}$	0011	4th	001011	6th
4th	= 1 + 3	= ${\displaystyle f_{1+1}+f_{1+3}}$	1011	4th	101011	6th
5	= 5	= ${\displaystyle f_{1+4}}$	00011	5	011011	6th
6th	= 1 + 5	= ${\displaystyle f_{1+1}+f_{1+4}}$	10011	5	000111	6th
7th	= 2 + 5	= ${\displaystyle f_{1+2}+f_{1+4}}$	01011	5	100111	6th
8th	= 8	= ${\displaystyle f_{1+5}}$	000011	6th	010111	6th
9	= 1 + 8	= ${\displaystyle f_{1+1}+f_{1+5}}$	100011	6th	00001011	8th
10	= 2 + 8	= ${\displaystyle f_{1+2}+f_{1+5}}$	010011	6th	10001011	8th
11	= 3 + 8	= ${\displaystyle f_{1+3}+f_{1+5}}$	001011	6th	01001011	8th
12	= 1 + 3 + 8	= ${\displaystyle f_{1+1}+f_{1+3}}$           ${\displaystyle +f_{1+5}}$	101011	6th	10001011	8th
13	= 13	= ${\displaystyle f_{1+6}}$	0000011	7th	10101011	8th
89		= ${\displaystyle f_{1+10}}$	00000000011	11	010100001011	12
832040		= ${\displaystyle f_{1+29}}$	000000000000 000000000000 000011	30th	010100000010 100100000110 1011	28
1134903170		= ${\displaystyle f_{1+44}}$	000000000000 000000000000 000000000000 000000011	45	010001001010 100000011010 010000100101 0111	40

In this way it becomes, for example, that of 4 code words

existing sequence of numbers	1, 3, 7, 12
in Fibonacci code as	11001101011101011
and in the ternary comma code as	101100101110011110001011

shown, whereby the commas are set in smaller letters just to make it easier to separate the code words.

To represent a natural number in Fibonacci code, proceed as follows: ${\displaystyle N}$

1. Find the largest Fibonacci number and find the difference ${\displaystyle f_{i}\leq N}$ ${\displaystyle N^{\prime }:=N-f_{i}.}$
2. Form a bit sequence consisting of zeros and add a one to the right. Go to step 4. ${\displaystyle i\!-\!1}$
3. Find the largest Fibonacci number and find the difference ${\displaystyle f_{i}\leq N}$ ${\displaystyle N^{\prime }:=N-f_{i}.}$
4. Write a one at the -th position in the bit sequence (the first position in the bit sequence is on the far left and has the index 1). ${\displaystyle (i\!-\!1)}$
5. Is go to step 3 and continue. Otherwise you're done. ${\displaystyle N^{\prime }>0,}$ ${\displaystyle N:=N^{\prime }}$

To decode a Fibonacci code, one looks for the next double one (the comma) further to the right and removes the second one (immediately following), after which the next code word begins (it can start with a third one). What remains is the Zeckendorf sequence of the coded number. Their value is the sum of the Fibonacci numbers 1, 2, 3, 5, 8, 13 ... at whose index in the Zeckendorf sequence there is a one.

This means that a message can be clearly broken down into its code words and the Fibonacci code is a prefix code . In addition, it is a so-called universal prefix code because it encodes natural numbers and the expected value of the length of the code word falls monotonically with the size of the coded number.

Fibonacci multiplication

From the Zeckendorf representations

${\displaystyle m=:\sum _{i=1}^{k}f_{c_{i}}}$   with     and   ${\displaystyle k\geq 0}$ ${\displaystyle 0\ll c_{1}\ll c_{2}\ll \dotsc \ll c_{k}}$

and

${\displaystyle n=:\sum _{j=1}^{l}f_{d_{j}}}$   with     and   ${\displaystyle l\geq 0}$ ${\displaystyle 0\ll d_{1}\ll d_{2}\ll \dotsc \ll d_{l}}$

two natural numbers where the relation should stand for the sake of brevity , the Fibonacci product (at Knuth circle multiplication , German roughly Kringel product ) ${\displaystyle m,n,}$ ${\displaystyle c\ll d}$ ${\displaystyle c\leq d-2}$

${\displaystyle m\circ n:=\sum _{i=1}^{k}\sum _{j=1}^{l}f_{c_{i}+d_{j}}}$

of and form. For example, the Zeckendorf representation is of 2 and that of 4. Thus, For pure Fibonacci numbers is ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle f_{3}}$ ${\displaystyle f_{4}\!+\!f_{2}}$ ${\displaystyle 2\circ 4=f_{3+4}+f_{3+2}=13+5=18.}$

${\displaystyle f_{c}\circ f_{d}=f_{c+d}}$

and using the approximation formula for large indices

${\displaystyle f_{c}\circ f_{d}=\left[{\frac {\Phi ^{c}}{\sqrt {5}}}\right]\circ \left[{\frac {\Phi ^{d}}{\sqrt {5}}}\right]=f_{c+d}=\left[{\frac {\Phi ^{c+d}}{\sqrt {5}}}\right]\approx {\sqrt {5}}\cdot f_{c}\cdot f_{d},}$

from which the estimate for large is derived. But it is closer to the higher and closer to the lower ${\displaystyle m,n}$ ${\displaystyle m\circ n\approx {\sqrt {5}}\,mn\approx 2{,}236\,mn}$ ${\displaystyle 1\circ n}$ ${\displaystyle \Phi ^{2}n\approx 2{,}618\,n}$ ${\displaystyle 2\circ n}$ ${\displaystyle \Phi ^{3}n\approx 2{,}118\,(2n).}$

Multiplication table †
${\displaystyle \circ }$	Fibonacci code	1	2	3	4th	5	6th	7th	8th	9	10	11	12	13
1	11	3	5	8th	11	13	16	18th	21st	24	26th	29	32	34
2	011	5	8th	13	18th	21st	26th	29	34	39	42	47	52	55
3	0011	8th	13	21st	29	34	42	47	55	63	68	76	84	89
4th	1011	11	18th	29	40	47	58	65	76	87	94	105	116	123
5	00011	13	21st	34	47	55	68	76	89	102	110	123	136	144
6th	10011	16	26th	42	58	68	84	94	110	126	136	152	168	178
7th	01011	18th	29	47	65	76	94	105	123	141	152	170	188	199
8th	000011	21st	34	55	76	89	110	123	144	165	178	199	220	233
9	100011	24	39	63	87	102	126	141	165	189	204	228	252	267
10	010011	26th	42	68	94	110	136	152	178	204	220	246	272	288
11	001011	29	47	76	105	123	152	170	199	228	246	275	304	322
12	101011	32	52	84	116	136	168	188	220	252	272	304	336	356
13	0000011	34	55	89	123	144	178	199	233	267	288	322	356	377

^† Fibonacci numbers in italics

A simple rearrangement of the double sum proves the Fibonacci multiplication to be commutative . In 1988 Knuth showed that the associative law also applies exactly - and not just asymptotically or approximately.

In contrast to the algebraic structure, which is a monoid , has no neutral element, so it is only a (commutative) semigroup . In addition , it does not distribute via the addition , because it is e.g. ${\displaystyle \mathbb {N} ,}$ ${\displaystyle (\mathbb {N} ,\cdot ,1)}$ ${\displaystyle (\mathbb {N} ,\circ )}$ ${\displaystyle \circ }$ ${\displaystyle +}$

${\displaystyle (1+1)\circ 1=2\circ 1=5\quad \neq \quad 6=3+3=(1\circ 1)+(1\circ 1).}$

The Zeckendorf sequence of is the empty one, so that every product is also the empty sum. Thus an annihilating element is in the semigroup ${\displaystyle 0\in \mathbb {N} _{0}}$ ${\displaystyle 0\circ n}$ ${\displaystyle 0}$ ${\displaystyle (\mathbb {N} _{0},\circ ).}$

negaFibonacci representation

More general than the Zeckendorf theorem is the related statement that every integer can be represented uniquely as a (possibly empty) sum of different, not directly consecutive negaFibonacci numbers ( with ): ${\displaystyle z\in \mathbb {Z} }$ ${\displaystyle f_{-i}}$ ${\displaystyle i\geq 1}$

${\displaystyle z=\sum _{i=1}^{k}c_{i}f_{-i}}$with and for everyone . ${\displaystyle c_{i}\in \{0,1\}}$ ${\displaystyle c_{i}c_{i+1}=0}$ ${\displaystyle i}$

Examples:

${\displaystyle n}$	negaFibonacci representation		Binary digits
24	= 1 + (-3) + (-8) + 34	= ${\displaystyle f_{-1}+f_{-4}+f_{-6}+f_{-9}}$	100101001
12	= (-1) + 13	= ${\displaystyle f_{-2}+f_{-7}}$	0100001
4th	= (-1) + 5	= ${\displaystyle f_{-2}+f_{-5}}$	01001
3	= 1 + 2	= ${\displaystyle f_{-1}+f_{-3}}$	101
2		= ${\displaystyle f_{-3}}$	001
1		= ${\displaystyle f_{-1}}$	1
0		= (empty sum)	Ø
-1		= ${\displaystyle f_{-2}}$	01
-2	= 1 + (-3)	= ${\displaystyle f_{-1}+f_{-4}}$	1001
-3		= ${\displaystyle f_{-4}}$	0001
-4	= (-1) + (-3)	= ${\displaystyle f_{-2}+f_{-4}}$	0101
-5	= 1 + 2 + (–8)	= ${\displaystyle f_{-1}+f_{-3}+f_{-6}}$	101001
–11	= (-3) + (-8)	= ${\displaystyle f_{-4}+f_{-6}}$	000101
-43	= (-1) + 13 + (-55)	= ${\displaystyle f_{-2}+f_{-7}+f_{-10}}$	0100001001

In the case of positive whole numbers, the representations have an odd number of digits and in the case of negative integers, even.

As with the Zeckendorf representation, there are no 2 ones in a row. All representations except that of the ends in a one. Adding a one as a comma turns the bit strings of the negaFibonacci representation into a prefix code for whole. In the event that this is also to be coded, the reversible conversion can be used ${\displaystyle 0}$ ${\displaystyle \mathbb {Z} \!\setminus \!\{0\}.}$ ${\displaystyle 0}$

${\displaystyle \mathbb {Z} \to \mathbb {Z} \!\setminus \!\{0\},\quad z\mapsto {\begin{cases}z,&{\text{ wenn }}z>0\\z-1,&{\text{ wenn }}z\leq 0\end{cases}}}$

switch between. But if the conversion is done anyway, you can do it right away

${\displaystyle \mathbb {Z} \to \mathbb {N} ,\qquad z\mapsto {\begin{cases}\;\;2z,&{\text{ wenn }}z>0\\-2z+1,&{\text{ wenn }}z\leq 0\end{cases}}}$

and take the Fibonacci coding .

Individual evidence

1. ^ Eric W. Weisstein : Zeckendorf Representation . In: MathWorld (English).
2. ↑ Cornelis Gerrit Lekkerkerker: Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci (representation of the natural numbers as a sum of Fibonacci numbers) . In: Simon Stevin . 29, 1952, pp. 190-195. .
3. ↑ R. Knott: 4.2 Historical Note on the name "Zeckendorf Representation" ( historical note on naming the Zeckendorf representation ), University of Surrey
4. ↑ assuming little-endian notation
5. ↑ From this it follows by the way what in turn results in the existence and uniqueness of the Zeckendorf sequence. ${\displaystyle N^{\prime }<f_{i-1},}$
6. ^ Jean-Paul Allouche, Jeffrey Shallit: Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press , 2003, ISBN 978-0-521-82332-6 , p. 105.
7. ↑ Aviezri S. Fraenkel, Shmuel T. Klein: Robust universal complete codes for transmission and compression . In: Discrete Applied Mathematics . 64, No. 1, 1996, ISSN  0166-218X , pp. 31-55. doi : 10.1016 / 0166-218X (93) 00116-H .
8. ↑ On the Usefulness of Fibonacci Compression Codes Shmuel T. Klein, Miri Kopel Ben-nissan: On the Usefulness of Fibonacci Compression Codes (2004) . In: The Computer Journal . 00, No. 0, 2005, ISSN  0166-218X , pp. 1-15.
9. ^ Donald E. Knuth : Fibonacci multiplication . In: Applied Mathematics Letters . 1, No. 1, 1988, ISSN  0893-9659 , pp. 57-60. doi : 10.1016 / 0893-9659 (88) 90176-0 .
10. ↑ Donald E. Knuth: The Art Of Computer Programming, Vol. IV .