Additionskette

Eine Additionskette für eine positive ganze Zahl ${\displaystyle n}$ ist eine endliche Folge positiver ganzer Zahlen, die mit 1 beginnt und mit ${\displaystyle n}$ endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Für fast alle Fragestellungen genügt es, streng monoton steigende Folgen zu betrachten, so dass die Monotonie oft mit gefordert wird (siehe Varianten der Definition).

Unter der Länge einer Additionskette versteht man die Anzahl der Folgenglieder, die Summe vorangegangener Folgenglieder sind – die 1 am Anfang wird also nicht mitgezählt. Ist ${\displaystyle r}$ die Länge der Additionskette ${\displaystyle (a_{i})_{i=0,\cdots ,r}}$ für ${\displaystyle n}$, so ist ${\displaystyle a_{0}=1,a_{1}=2,\cdots ,a_{r}=n}$. Die minimale Länge aller Additionsketten für ${\displaystyle n}$ wird mit ${\displaystyle l(n)}$ bezeichnet.

Beispiel:

• (1, 2, 4, 5, 9) ist eine Additionskette der Länge 4 für 9, denn 2 = 1+1, 4 = 2+2, 5 = 4+1 und 9 = 5+4.
• (1, 2, 4, 6, 9) ist keine Additionskette für 9, denn 9 ist nicht Summe zweier vorangegangener Folgenglieder.

${\displaystyle l(9)=4}$, denn es gibt keine kürzere Additionskette für 9. Andere Additionsketten für 9 sind gleich lang (zwei weitere) oder länger.