Satz von Zeckendorf
Der nach Edouard Zeckendorf benannte Satz von Zeckendorf (auch: Zeckendorf-Theorem) besagt, dass jede natürliche Zahl eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen mit Indizes geschrieben werden kann. Das heißt, es gibt für jedes eine eindeutige Darstellung der Form
mit und für alle .[1] Die entstehende Folge von Nullen und Einsen wird Zeckendorf-Sequenz (auch: Zeckendorf-Darstellung) genannt.
Historische Anmerkung
Während das Theorem nach Zeckendorf, einem Autor, der es im Jahr 1972 publizierte, (eponymisch) benannt ist, ist genau dieses Ergebnis 20 Jahre früher von Gerrit Lekkerkerker[2] veröffentlicht worden. Demnach ist der Satz von Zeckendorf ein Beispiel für Stiglers Gesetz der Eponyme.[3]
Herleitung
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Zeckendorf_representations_89px.png/267px-Zeckendorf_representations_89px.png)
Die Breite (blau in der Mitte) eines Rechtecks ist eine Fibonacci-Zahl , und seine Höhe.
Rechtecke gleicher Farbe sind kongruent.
In der Grafik ist die 45°-schräge Diagonale eine gerasterte Treppe nach rechts unten. Das ganzzahlige Raster sei nach unten als Ordinate, nach rechts als Abszisse aufgefasst. Folgende Feststellungen lassen sich entnehmen:
(1) Jede natürliche Zahl kommt als Ordinate vor – und damit auch als Abszisse. (2) Die verschiedenfarbigen Rechtecke zerteilen eine durch eine Ordinate spezifizierte waagrechte Schicht der Höhe 1 von links nach rechts in Segmente strikt abnehmender Breite, jede Breite eine Fibonacci-Zahl.
Diese Eigenschaften gelten ersichtlich für den Induktionsanfang der Breite=Höhe=. Wir beginnen die Induktion links oben in der Spitze des Dreiecks. Alle Dreiecke sind gleichschenklig-rechtwinklig.
Induktionsannahme: Die Zeckendorf-Darstellung ist für alle Dreiecke bis einschließlich des Formats Abszisse=Ordinate= möglich.
Im Induktionsschritt wird unterhalb dieses Dreiecks ein Rechteck des (um 1 breiteren) Formats Breite= Höhe= angefügt, an welches rechts mit bündiger Grundseite ein gleichschenklig-rechtwinkliges Dreieck des Formats Breite=Höhe= gefügt wird, und zwar eine Kopie der bisherigen Spitze. Die Gesamtbreite ist nach den Anfügungen Zusammen mit dem Dreieck der Induktionsannahme ergibt sich ein Dreieck der Höhe=, die – wie erwartet – mit der Breite übereinstimmt.
Die beiden oben gemachten Feststellungen gelten nach den Anfügungen genauso wie vorher. Aus der ersten (1) folgt das Auftreten jeder natürlichen Zahl als Ordinate – zunächst induktiv für die beim Induktionsschritt hinzukommenden natürlichen Zahlen im Intervall dann zusammen mit der Induktionsannahme für jede natürliche Zahl
Aus der zweiten (2) folgt, dass die Breiten der Rechtecke, die rechts an einem großen Rechteck anliegen, Fibonacci-Zahlen sind und diese stets echt kleiner sind als die Höhe des großen Rechtecks. D. h., jedes Rechteck ist echt schmaler, als das Rechteck zu seiner Linken hoch ist. Das hat zur Folge, dass die Breiten als Fibonacci-Zahlen nach rechts um mindestens zwei Indexstufen abnehmen. Die Segmentierung ist somit eine Zeckendorf-Darstellung.
Das folgende Lemma garantiert die Eindeutigkeit der Darstellung:
- Die Summe einer nicht-leeren Menge verschiedener und nicht aufeinander folgender Fibonacci-Zahlen, deren größte ist, ist echt kleiner als die nächstgrößere Fibonacci-Zahl
Fibonacci-Kode
Da bei der Zeckendorf-Sequenz aufeinanderfolgende Fibonacci-Zahlen ausgeschlossen sind, können keine zwei Einsen in einer Zeckendorf-Sequenz unmittelbar hintereinander stehen. Der Fibonacci-Kode entsteht aus der Zeckendorf-Sequenz, die rechts[4] mit einer höchstwertigen Eins (1
) endet, durch Anhängen einer weiteren 1
(ohne Stellenwert). Die Doppeleins 11
spielt die Rolle des Kommas, das die (aus natürlichen Zahlen bestehenden) Kodewörter in einer variabel langen Kodierung voneinander trennt.
Der Fibonacci-Kode steht damit in direkter Konkurrenz zum binär kodierten ternären Komma-Kode, bei dem ein „Trit“ durch zwei Bits (00
=: 0, 10
=: 1 und 01
=: 2 ) dargestellt wird und die Doppeleins 11
die Rolle des Kommas spielt. Bei einer angenommenen geometrischen Verteilung der natürlichen Zahlen ist beim Fibonacci-Kode
(mit als dem Goldenen Schnitt) und beim ternären Komma-Kode
- .
Der letztere ist also asymptotisch etwas kürzer, aber bei den sehr kleinen und meistens häufigeren Zahlen etwas länger.
Für kleine natürliche Zahlen sind in der Tabelle die beiden Kodes gegenübergestellt, jeweils mit Angabe ihrer Länge in Bits. Aus dieser Länge errechnet sich eine Wahrscheinlichkeitsverteilung, die sog. implizierte (engl. implied probability distribution), , für die der Kode nahezu optimal ist. Beide Kodes beginnen links mit dem niedrigstwertigen Bit, sind also little-endian notiert. (In diesem Artikel beginnt die Indizierung des Fibonacci-Kodes mit 1, wogegen der Ternär-Kode wie bei Stellenwertsystemen üblich mit dem Index (und Exponenten) 0 starten soll. Die Fibonacci-Zahlen, um die es hier geht, beginnen mit so dass die Fibonacci-Zahl in der Zeckendorf-Sequenz mit der linkesten Stelle (am Index 1) korrespondiert.)
Zeckendorf-Darstellung Fibonacci-Kode ternär mit Komma 1 = 1 = 11
2 1011
4 2 = 2 = 011
3 0111
4 3 = 3 = 0011
4 001011
6 4 = 1+3 = 1011
4 101011
6 5 = 5 = 00011
5 011011
6 6 = 1+5 = 10011
5 000111
6 7 = 2+5 = 01011
5 100111
6 8 = 8 = 000011
6 010111
6 9 = 1+8 = 100011
6 00001011
8 10 = 2+8 = 010011
6 10001011
8 11 = 3+8 = 001011
6 01001011
8 12 = 1+3+8 =
101011
6 10001011
8 13 = 13 = 0000011
7 10101011
8 89 = 00000000011
11 010100001011
12 832040 = 000000000000
000000000000
000011
30 010100000010
100100000110
1011
28 1134903170 = 000000000000
000000000000
000000000000
000000011
45 010001001010
100000011010
010000100101
0111
40
Auf diese Weise wird beispielsweise die aus 4 Kodewörtern
bestehende Zahlenfolge | 1, 3, 7, 12 |
im Fibonacci-Kode als | 11001101011101011 |
und im ternären Komma-Kode als | 101100101110011110001011 |
dargestellt, wobei nur um der leichteren Trennung der Kodewörter willen die Kommata in kleinerer Schrift gesetzt sind.
Um eine natürliche Zahl im Fibonacci-Kode darzustellen, geht man folgendermaßen vor:
- Finde die größte Fibonacci-Zahl und bilde die Differenz [5]
- Bilde eine Bitsequenz bestehend aus Nullen und hänge rechts eine Eins dran. Gehe zu Schritt 4.
- Finde die größte Fibonacci-Zahl und bilde die Differenz
- Schreibe an die -te Stelle in der Bitsequenz eine Eins (dabei ist die erste Stelle der Bitsequenz ganz links und hat den Index 1).
- Ist fahre mit Schritt 3 und fort. Andernfalls ist man fertig.
Um einen Fibonacci-Kode zu dekodieren, sucht man weiter rechts die nächste Doppeleins (das Komma) und entfernt davon die (direkt darauf folgende) zweite Eins, hinter der das nächste Kodewort beginnt (es kann mit einer dritten Eins beginnen). Übrig bleibt die Zeckendorf-Sequenz der kodierten Zahl. Deren Wert ist die Summe der Fibonacci-Zahlen 1, 2, 3, 5, 8, 13 …, an deren Index in der Zeckendorf-Sequenz sich eine Eins befindet.
Somit ist eine Nachricht eindeutig in ihre Kodewörter zerlegbar und der Fibonacci-Kode ein Präfixkode. Darüber hinaus ist er ein sog. universeller Präfixkode, weil er natürliche Zahlen kodiert und der Erwartungswert der Länge des Kodewortes monoton mit der Größe der kodierten Zahl fällt.[6][7][8]
Fibonacci-Multiplikation
Aus den Zeckendorf-Darstellungen
- mit und
und
- mit und
zweier natürlicher Zahlen wobei die Relation der Kürze halber für stehen soll, lässt sich das Fibonacci-Produkt (bei Knuth[9] circle multiplication, deutsch etwa Kringel-Produkt)
von und bilden. Beispielsweise ist die Zeckendorf-Darstellung von 2 und die von 4. Somit ist Für reine Fibonacci-Zahlen ist
und anhand der Näherungsformel für große Indizes
woraus sich für große die Abschätzung ableitet. Es ist aber näher beim höheren und näher beim niedrigeren
Multiplikationstafel† Fibona-
cci-Kode1 2 3 4 5 6 7 8 9 10 11 12 13 1 11 3 5 8 11 13 16 18 21 24 26 29 32 34 2 011 5 8 13 18 21 26 29 34 39 42 47 52 55 3 0011 8 13 21 29 34 42 47 55 63 68 76 84 89 4 1011 11 18 29 40 47 58 65 76 87 94 105 116 123 5 00011 13 21 34 47 55 68 76 89 102 110 123 136 144 6 10011 16 26 42 58 68 84 94 110 126 136 152 168 178 7 01011 18 29 47 65 76 94 105 123 141 152 170 188 199 8 000011 21 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 26 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-Zahlen kursiv gesetzt
Eine einfache Umordnung der Doppelsumme erweist die Fibonacci-Multiplikation als kommutativ. Knuth hat 1988 gezeigt, dass auch das Assoziativgesetz exakt gilt – und nicht nur asymptotisch oder näherungsweise.
Im Unterschied zur algebraischen Struktur die als ein Monoid ist, hat kein neutrales Element, ist also nur eine (kommutative) Halbgruppe. Außerdem distributiert nicht über die Addition , denn es ist bspw.
Die Zeckendorf-Sequenz von ist die leere, so dass auch jedes Produkt die leere Summe ist. Somit ist annihilierendes Element in der Halbgruppe
negaFibonacci-Darstellung
Allgemeiner als das Zeckendorf-Theorem ist die verwandte Aussage, dass sich jede ganze Zahl eindeutig als (möglicherweise leere) Summe verschiedener, nicht direkt aufeinanderfolgender negaFibonacci-Zahlen ( mit ) darstellen lässt:[10]
- mit und für alle .
Beispiele:
negaFibonacci-Darstellung Binärziffern 24 = 1 + (–3) + (–8) + 34 = 100101001
12 = (–1) + 13 = 0100001
4 = (–1) + 5 = 01001
3 = 1 + 2 = 101
2 = 001
1 = 1
0 = (leere Summe) Ø
–1 = 01
–2 = 1 + (–3) = 1001
–3 = 0001
–4 = (–1) + (–3) = 0101
–5 = 1 + 2 + (–8) = 101001
–11 = (–3) + (–8) = 000101
–43 = (–1) + 13 + (–55) = 0100001001
Bei positiven ganzen Zahlen haben die Darstellungen ungerade Stellenzahl und bei negativen gerade.
Wie bei der Zeckendorf-Darstellung gibt es keine 2 Einsen hintereinander. Alle Darstellungen außer der der enden in einer Eins. Das Anhängen einer Eins als Komma macht aus den Bitketten der negaFibonacci-Darstellung einen Präfixkode für ganz Für den Fall, dass auch die zu kodieren ist, kann man die reversible Umrechnung
zwischenschalten. Wenn aber ohnehin umgerechnet wird, kann man auch gleich
und die Fibonacci-Kodierung nehmen.
Einzelnachweise
- ↑ Eric W. Weisstein: Zeckendorf Representation. In: MathWorld (englisch).
- ↑ Cornelis Gerrit Lekkerkerker: Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci (Darstellung der natürlichen Zahlen als eine Summe von Fibonacci-Zahlen). In: Simon Stevin. 29. Jahrgang, 1952, S. 190–195 (niederländisch). .
- ↑ R. Knott: 4.2 Historical Note on the name "Zeckendorf Representation" (Historische Anmerkung zur Namensgebung Zeckendorf-Darstellung), University of Surrey
- ↑ unter der Annahme der little-endian Notation
- ↑ Daraus folgt nebenbei was wiederum Existenz und Eindeutigkeit der Zeckendorf-Sequenz zur Folge hat.
- ↑ Jean-Paul Allouche, Jeffrey Shallit: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003, ISBN 978-0-521-82332-6, S. 105.
- ↑ Aviezri S. Fraenkel, Shmuel T. Klein: Robust universal complete codes for transmission and compression. In: Discrete Applied Mathematics. 64. Jahrgang, Nr. 1, 1996, ISSN 0166-218X, S. 31–55, doi:10.1016/0166-218X(93)00116-H.
- ↑ 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. Jahrgang, Nr. 0, 2005, ISSN 0166-218X, S. 1–15.
- ↑ Donald E. Knuth: Fibonacci multiplication. In: Applied Mathematics Letters. 1. Jahrgang, Nr. 1, 1988, ISSN 0893-9659, S. 57–60, doi:10.1016/0893-9659(88)90176-0 (umb.edu [PDF]).
- ↑ Donald E. Knuth: The Art Of Computer Programming, Vol. IV.