Satz von Zeckendorf
# Satz von Zeckendorf

Der nach Edouard Zeckendorf benannte Satz von Zeckendorf (auch: Zeckendorf-Theorem) besagt, dass jede natürliche Zahl $n>0$ eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen $f_{i}$ mit Indizes $i\geq 2$ geschrieben werden kann. Das heißt, es gibt für jedes $n\in \mathbb {N}$ eine eindeutige Darstellung der Form

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

mit $c_{i}\in \{0,1\}$ und $c_{i}c_{i+1}=0$ für alle $i$. Die entstehende Folge $\left(c_{i}\right)_{i\in 1+\mathbb {N} }$ 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 veröffentlicht worden. Demnach ist der Satz von Zeckendorf ein Beispiel für Stiglers Gesetz der Eponyme.

## Herleitung

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=$1$. 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=$f_{i}\!\!-\!\!1$ möglich.

Im Induktionsschritt wird unterhalb dieses Dreiecks ein Rechteck des (um 1 breiteren) Formats   Breite=$f_{i}\;\times$ Höhe=$f_{i-1}$   angefügt, an welches rechts mit bündiger Grundseite ein gleichschenklig-rechtwinkliges Dreieck des Formats   Breite=Höhe=$f_{i-1}\!\!-\!\!1$ gefügt wird, und zwar eine Kopie der bisherigen Spitze. Die Gesamtbreite ist nach den Anfügungen $f_{i}+(f_{i-1}\!\!-\!\!1)=f_{i+1}\!\!-\!\!1.$ Zusammen mit dem Dreieck der Induktionsannahme ergibt sich ein Dreieck der Höhe=$(f_{i}\!\!-\!\!1)+f_{i-1}=f_{i+1}\!\!-\!\!1$, 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 $[f_{i},f_{i+1}\!\!-\!\!1],$ dann zusammen mit der Induktionsannahme für jede natürliche Zahl $\leq f_{i+1}\!\!-\!\!1.$

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 $f_{i}$ ist, ist echt kleiner als die nächstgrößere Fibonacci-Zahl $f_{i+1}.$

## 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 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 $1/n^{q}$ der natürlichen Zahlen $n\in \mathbb {N}$ ist beim Fibonacci-Kode

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

(mit $\Phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618$ als dem Goldenen Schnitt) und beim ternären Komma-Kode

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

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 $n$ sind in der Tabelle die beiden Kodes gegenübergestellt, jeweils mit Angabe ihrer Länge $l(n)$ in Bits. Aus dieser Länge errechnet sich eine Wahrscheinlichkeitsverteilung, die sog. implizierte (engl. implied probability distribution), $p(n)=2^{-l(n)}$, 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 $f_{2}=1,f_{3}=2,$ so dass die Fibonacci-Zahl $f_{2}=1$ in der Zeckendorf-Sequenz mit der linkesten Stelle (am Index 1) korrespondiert.)

    $n$Zeckendorf-DarstellungFibonacci-Kode$l_{\mathrm {fib} }$ternär mit Komma$l_{\mathrm {tek} }$ 1= 1= $f_{1+1}$11210114 2= 2= $f_{1+2}$011301114 3= 3= $f_{1+3}$001140010116 4= 1+3= $f_{1+1}+f_{1+3}$101141010116 5= 5= $f_{1+4}$0001150110116 6= 1+5= $f_{1+1}+f_{1+4}$1001150001116 7= 2+5= $f_{1+2}+f_{1+4}$0101151001116 8= 8= $f_{1+5}$00001160101116 9= 1+8= $f_{1+1}+f_{1+5}$1000116000010118 10= 2+8= $f_{1+2}+f_{1+5}$0100116100010118 11= 3+8= $f_{1+3}+f_{1+5}$0010116010010118 12= 1+3+8= $f_{1+1}+f_{1+3}$     $+f_{1+5}$1010116100010118 13= 13= $f_{1+6}$00000117101010118 89= $f_{1+10}$000000000111101010000101112 832040= $f_{1+29}$000000000000 000000000000 00001130010100000010 100100000110 101128 1134903170= $f_{1+44}$000000000000 000000000000 000000000000 00000001145010001001010 100000011010 010000100101 011140

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 $N$ im Fibonacci-Kode darzustellen, geht man folgendermaßen vor:

* Finde die größte Fibonacci-Zahl $f_{i}\leq N$ und bilde die Differenz $N^{\prime }:=N-f_{i}.$
* Bilde eine Bitsequenz bestehend aus $i\!-\!1$ Nullen und hänge rechts eine Eins dran. Gehe zu Schritt 4.
* Finde die größte Fibonacci-Zahl $f_{i}\leq N$ und bilde die Differenz $N^{\prime }:=N-f_{i}.$
* Schreibe an die $(i\!-\!1)$-te Stelle in der Bitsequenz eine Eins (dabei ist die erste Stelle der Bitsequenz ganz links und hat den Index 1).
* Ist $N^{\prime }>0,$ fahre mit Schritt 3 und $N:=N^{\prime }$ 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.

## Fibonacci-Multiplikation

Aus den Zeckendorf-Darstellungen

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

und

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

zweier natürlicher Zahlen $m,n,$ wobei die Relation $c\ll d$ der Kürze halber für $c\leq d-2$ stehen soll, lässt sich das Fibonacci-Produkt (bei Knuth circle multiplication, deutsch etwa Kringel-Produkt)

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

von $m$ und $n$ bilden. Beispielsweise ist $f_{3}$ die Zeckendorf-Darstellung von 2 und $f_{4}\!+\!f_{2}$ die von 4. Somit ist $2\circ 4=f_{3+4}+f_{3+2}=13+5=18.$ Für reine Fibonacci-Zahlen ist

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

und anhand der Näherungsformel für große Indizes

    $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},$

woraus sich für große $m,n$ die Abschätzung $m\circ n\approx {\sqrt {5}}\,mn\approx 2{,}236\,mn$ ableitet. Es ist aber $1\circ n$ näher beim höheren $\Phi ^{2}n\approx 2{,}618\,n$ und $2\circ n$ näher beim niedrigeren $\Phi ^{3}n\approx 2{,}118\,(2n).$

    Multiplikationstafel⁠ $\circ$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 $\mathbb {N} ,$ die als $(\mathbb {N} ,\cdot ,1)$ ein Monoid ist, hat $(\mathbb {N} ,\circ )$ kein neutrales Element, ist also nur eine (kommutative) Halbgruppe. Außerdem distributiert $\circ$ nicht über die Addition $+$, denn es ist bspw.

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

Die Zeckendorf-Sequenz von $0\in \mathbb {N} _{0}$ ist die leere, so dass auch jedes Produkt $0\circ n$ die leere Summe ist. Somit ist $0$ annihilierendes Element in der Halbgruppe $(\mathbb {N} _{0},\circ ).$

## negaFibonacci-Darstellung

Allgemeiner als das Zeckendorf-Theorem ist die verwandte Aussage, dass sich jede ganze Zahl $z\in \mathbb {Z}$ eindeutig als (möglicherweise leere) Summe verschiedener, nicht direkt aufeinanderfolgender negaFibonacci-Zahlen ($f_{-i}$ mit $i\geq 1$) darstellen lässt:

    $z=\sum _{i=1}^{k}c_{i}f_{-i}$ mit $c_{i}\in \{0,1\}$ und $c_{i}c_{i+1}=0$ für alle $i$.

Beispiele:

    $n$negaFibonacci-DarstellungBinärziffern 24= 1 + (–3) + (–8) + 34= $f_{-1}+f_{-4}+f_{-6}+f_{-9}$100101001 12= (–1) + 13= $f_{-2}+f_{-7}$0100001 4= (–1) + 5= $f_{-2}+f_{-5}$01001 3= 1 + 2= $f_{-1}+f_{-3}$101 2= $f_{-3}$001 1= $f_{-1}$1 0= (leere Summe)Ø –1= $f_{-2}$01 –2= 1 + (–3)= $f_{-1}+f_{-4}$1001 –3= $f_{-4}$0001 –4= (–1) + (–3)= $f_{-2}+f_{-4}$0101 –5= 1 + 2 + (–8)= $f_{-1}+f_{-3}+f_{-6}$101001 –11= (–3) + (–8)= $f_{-4}+f_{-6}$000101 –43= (–1) + 13 + (–55)= $f_{-2}+f_{-7}+f_{-10}$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 $0$ enden in einer Eins. Das Anhängen einer Eins als Komma macht aus den Bitketten der negaFibonacci-Darstellung einen Präfixkode für ganz $\mathbb {Z} \!\setminus \!\{0\}.$ Für den Fall, dass auch die $0$ zu kodieren ist, kann man die reversible Umrechnung

    $\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}}$

zwischenschalten. Wenn aber ohnehin umgerechnet wird, kann man auch gleich

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

und die Fibonacci-Kodierung nehmen.

