Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Additionskette aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Additionskette

Eine Additionskette für ein $n\; \backslash in\; \backslash mathbb\{N\}^+$ ist eine endliche, _monoton_steigende Folge positiver, ganzer Zahlen $a\_0\; ...\; a\_r$ mit $a\_0\; =\; 1,\; a\_r\; =\; n$ und für alle $i\; =\; 1,...,r$ gibt es j und k mit , so dass $a\_i\; =\; a\_j\; +\; a\_k$. r bezeichnen wir als die Länge der Additionskette. Es bezeichne weiter l(n) die minimale Länge einer Additionskette für n.

Erklärung

Additionsketten sind Folgen von natürlichen Zahlen, also mehrere Zahlen $a\_0,\; a\_1,\; ...,\; a\_r$, die durch Komma getrennt notiert werden. Bei den Additionsketten setzt man voraus, dass die erste dieser Zahlen, $a\_0$, gleich 1 ist. Die nächste Zahl der Kette wird immer aus der Summe von genau zwei beliebigen Nummern gebildet, die schon in der Kette stehen, dies kann auch zweimal die gleiche Zahl sein (siehe Beispiel). $a\_1$ muss also 2 sein, da es nur die Summe von $a\_0$ und nochmal $a\_0$ sein kann. Die nächste Zahl wird wieder aus der Summe von exakt zwei beliebigen Vorgängern gebildet, $a\_2$ ist somit 2 (zweimal $a\_0$) oder 3 ($a\_0\; +\; a\_1$) oder 4 (zweimal $a\_1$). So verfährt man weiter, bis das letzte Element der Folge $a\_r$ erreicht ist. Dieses letzte Element ist das gewünschte Ziel der Additionskette. Weiterhin ist zu beachten, dass die Kette monoton steigend ist, d.h. eine Zahl darf nicht kleiner sein, als ihr Vorgänger.

Zu einer natürlichen Zahl gibt es meist mehrere Additionsketten, die diese als letztes Element enthalten (siehe Beispiel). Interessant sind besonders kürzeste Ketten, die eine bestimmte Zahl erreichen. l(n) gibt die Länge einer möglichen kürzesten Kette für eine Zahl n an. Zu beachten ist, dass die Länge einer Additionskette die Anzahl der zugehörigen Zahlen ohne das erste Element $a\_0\; (=1)$ ist.

Die meisten Zahlen (letztlich sogar fast alle, bezogen auf die richtige Wahl einer Dichte) lassen sich mittels einer Additionskette beschreiben, deren Länge in Abhängigkeit von der Zahl $n$ im wesentlichen $log\_2\; (n)\; +\; \backslash frac\{log\_2\; (n)\}\{log\_2(log\_2(n))\}$ ist.

Beispiel

Eine Additionskette für 6

1, 2 (=1+1), 3 (=1+2), 4 (=1+3), 6 (=2+4) mit der Länge 4eine kürzere Additionskette für 6

1, 2 (=1+1), 3 (=1+2), 6 (=3+3) mit der Länge 3die untere Kette ist zusammen mit 1,2,4,6 eine kürzeste für 6, also gilt

:l(6) = 3

       VIDEO-NEWS UND ANGEBOTE