Additionskette

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