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

Die Segmentierung einer waagrechten Schicht der Höhe 1 entspricht der Zeckendorf-Darstellung einer natürlichen Zahl < 89.
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-DarstellungFibonacci-Kodeternär mit Komma
1= 1= 11210114
2= 2= 011301114
3= 3= 001140010116
4= 1+3= 101141010116
5= 5= 0001150110116
6= 1+5= 1001150001116
7= 2+5= 0101151001116
8= 8= 00001160101116
9= 1+8= 1000116000010118
10= 2+8= 0100116100010118
11= 3+8= 0010116010010118
12= 1+3+8=
         
1010116100010118
13= 13= 00000117101010118
89= 000000000111101010000101112
832040= 000000000000
000000000000
000011
30010100000010
100100000110
1011
28
1134903170= 000000000000
000000000000
000000000000
000000011
45010001001010
100000011010
010000100101
0111
40

Auf diese Weise wird beispielsweise die aus 4 Kodewörtern

bestehende Zahlenfolge1, 3, 7, 12
im Fibonacci-Kode als11001101011101011
und im ternären Komma-Kode als101100101110011110001011

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:

  1. Finde die größte Fibonacci-Zahl und bilde die Differenz [5]
  2. Bilde eine Bitsequenz bestehend aus Nullen und hänge rechts eine Eins dran. Gehe zu Schritt 4.
  3. Finde die größte Fibonacci-Zahl und bilde die Differenz
  4. Schreibe an die -te Stelle in der Bitsequenz eine Eins (dabei ist die erste Stelle der Bitsequenz ganz links und hat den Index 1).
  5. 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-Kode
12345678910111213
11135811131618212426293234
2011581318212629343942475255
300118132129344247556368768489
4101111182940475865768794105116123
5000111321344755687689102110123136144
61001116264258688494110126136152168178
701011182947657694105123141152170188199
80000112134557689110123144165178199220233
910001124396387102126141165189204228252267
1001001126426894110136152178204220246272288
11001011294776105123152170199228246275304322
12101011325284116136168188220252272304336356
130000011345589123144178199233267288322356377
 
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-DarstellungBinä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

  1. Eric W. Weisstein: Zeckendorf Representation. In: MathWorld (englisch).
  2. 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)..
  3. R. Knott: 4.2 Historical Note on the name "Zeckendorf Representation" (Historische Anmerkung zur Namensgebung Zeckendorf-Darstellung), University of Surrey
  4. unter der Annahme der little-endian Notation
  5. Daraus folgt nebenbei was wiederum Existenz und Eindeutigkeit der Zeckendorf-Sequenz zur Folge hat.
  6. Jean-Paul Allouche, Jeffrey Shallit: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003, ISBN 978-0-521-82332-6, S. 105.
  7. 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.
  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. Jahrgang, Nr. 0, 2005, ISSN 0166-218X, S. 1–15.
  9. 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]).
  10. Donald E. Knuth: The Art Of Computer Programming, Vol. IV.

Auf dieser Seite verwendete Medien

Zeckendorf representations 89px.png
The segmentation of a line is the Zeckendorf representation of the line's width