Additionskette

Eine Additionskette für ein n \in \mathbb{N}^+ ist eine endliche, monoton steigende Folge positiver, ganzer Zahlen a0...ar mit a0 = 1,ar = n und für alle i = 1,...,r gibt es j und k mit k \le j < i, so dass ai = aj + ak. 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 a0,a1,...,ar, die durch Komma getrennt notiert werden. Bei den Additionsketten setzt man voraus, dass die erste dieser Zahlen, a0, 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). a1 muss also 2 sein, da es nur die Summe von a0 und nochmal a0 sein kann. Die nächste Zahl wird wieder aus der Summe von exakt zwei beliebigen Vorgängern gebildet, a2 ist somit 2 (zweimal a0) oder 3 (a0 + a1) oder 4 (zweimal a1). So verfährt man weiter, bis das letzte Element der Folge ar 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 a0( = 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) + \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 4


eine kürzere Additionskette für 6

1, 2 (=1+1), 3 (=1+2), 6 (=3+3) mit der Länge 3


die untere Kette ist zusammen mit 1,2,4,6 eine kürzeste für 6, also gilt

l(6) = 3

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Alfred Brauer — Alfred Theodor Brauer Alfred Theodor Brauer (* 9. April 1894 in Berlin Charlottenburg; † 23. Dezember 1985 in Chapel Hill, North Carolina) war ein deutsch US amerikanischer Mathematiker jüdischer Herkunft. Durch die Teilnahme am Kriegsgeschehen… …   Deutsch Wikipedia

  • Alfred T. Brauer — Alfred Theodor Brauer Alfred Theodor Brauer (* 9. April 1894 in Berlin Charlottenburg; † 23. Dezember 1985 in Chapel Hill, North Carolina) war ein deutsch US amerikanischer Mathematiker jüdischer Herkunft. Durch die Teilnahme am Kriegsgeschehen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”