Benutzer:Lantani/Additionskette

Diese Entwurfsseite soll später in den Artikel Additionskette eingearbeitet werden.

Eine Additionskette für eine positive ganze Zahl $n$ ist eine endliche Folge positiver ganzer Zahlen, die mit 1 beginnt und mit $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 $r$ die Länge der Additionskette $(a_{i})_{i=0,\cdots ,r}$ für $n$ , so ist $a_{0}=1,a_{1}=2,\cdots ,a_{r}=n$ . Die minimale Länge aller Additionsketten für $n$ wird mit $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.

$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.

Aufbau von Additionsketten

Varianten der Definition

Die eingangs angegebene Definition einer Additionskette ist die ursprüngliche^[1]^[2] und wird daher meist zugrunde gelegt. Bei ihr treten die Zahlen nicht notwendig in aufsteigender Reihenfolge auf; so sind etwa (1, 2, 3, 4, 8, 11), (1, 2, 4, 3, 8, 11) und (1, 2, 4, 8, 3, 11) drei verschiedene Additionsketten, die dieselben Summen derselben Glieder enthalten und sich nur in der Reihenfolge der Summenbildungen unterscheiden. In aller Regel interessiert man sich aber für die Reihenfolge nicht, sondern betrachtet die drei Ketten als Varianten derselben Kette, genauer: als Repräsentanten derselben Äquivalenzklasse von Ketten. Diese ist dann allein durch die (ungeordnete) Menge der Glieder gegeben: Genau dann, wenn eine endliche Menge $A$ positiver ganzer Zahlen die Menge der Kettenglieder einer Additionskette (also die Bildmenge der Folge) ist, gilt $1\in A$ und $A\setminus \{1\}\subset \{x+y:x,y\in A\}$ . Dann aber ist insbesondere die eindeutig bestimmte streng monoton steigende, ab 0 indizierte Folge der Elemente von $A$ eine Additionskette für $n=\max A$ . Es kann weitere Additionsketten für dieses $n$ geben, die aus derselben Menge von Gliedern in anderer Reihenfolge bestehen; diese lassen sich aber leicht aus $A$ konstruieren. Oft werden deshalb nur die streng monoton steigenden Additionsketten genauer untersucht, z. B. bei Knuth:^[3] „Wir können ohne Beschränkung der Allgemeinheit annehmen, dass eine Additionskette aufsteigend ist, […] Von jetzt an werden wir nur aufsteigende Ketten betrachten, ohne diese Ausnahme explizit zu erwähnen.“

Aufzählung von Additionsketten

0	1	2	3	4	5 (nur für 15)	5 (nur für 11)
1	1, 2	1, 2, 3	1, 2, 3, 4	…, 5 \| 6 \| 7 \| 8		…, 7, 11 \| 8, 11
			1, 2, 3, 5	…, 6 \| 7 \| 8 \| 10	…, 10 , 15	…, 6, 11 \| 8, 11 \| 10, 11
			1, 2, 3, 6	…, 7 \| 8 \| 9 \| 12	…, 9, 15 \| 12, 15	…, 8, 11 \| 9, 11
		1, 2, 4	1, 2, 4, 5	…, 6 \| 7 \| 8 \| 9 \| 10	…, 10, 15	…, 6, 11 \| 7, 11 \| 9, 11 \| 10, 11
			1, 2, 4, 6	…, 7 \| 8 \| 10 \| 12		…, 7, 11 \| 10, 11
			1, 2, 4, 8	…, 9 \| 10 \| 12 \| 16		…, 9, 11 \| 10, 11

In dieser Tabelle stehen alle Additionsketten der Länge bis 4 sowie eine Auswahl der insgesamt 135 Ketten der Länge 5, nämlich diejenigen, deren Endglied entweder 15 oder 11 ist. Der senkrechte Strich „|“ trennt alternative Teilketten. Das Auslassungszeichen „…“ bedeutet immer die Kette der Länge 3 in derselben Tabellenzeile. Die Endglieder sind fettgedruckt, wo sie in einer kürzesten Kette für diese Zahl erscheinen.

Auf diese Weise kann man im Prinzip alle Additionsketten aufzählen und erhält damit zu jeder Zahl eine kürzeste, alle kürzesten oder auch alle überhaupt. Ohne weiteres praktikabel ist dieses Verfahren aber nur für kleine Zahlen: Bereits mit der Länge 10 gibt es über 10 Millionen^[4] verschiedene Additionsketten, und ihre Zahl wächst rasch weiter.

Die Anfangsabschnitte einer kürzesten Kette sind nicht notwendig selbst kürzeste Ketten für ihr jeweiliges Endglied. So beginnen die Ketten für 7 und 11 in der obersten Tabellenzeile mit (1, 2, 3, 4), was keine kürzeste Kette ist. Es genügt also nicht, bei der Konstruktion von kürzesten Ketten für ein $n$ nur die kürzesten Ketten für die Zahlen $<n$ heranzuziehen.

Summandenschreibweise	Anz.	erzeugte Ketten
1, 2, 3, 4 → {+3, +4} → 11	2	1, 2, 3, 4, (7 \| 8), 11
1, 2 → {+1, +2} → 5 → {+1, +5} → 11	4	1, 2, (3 \| 4), 5, (6 \| 10), 11
1, 2, 3 → {+2, +3, +3} → 11	3	1, 2, 3, (5, 8 \| 6, 8 \| 6, 9), 11
1, 2, 4 → {+1, +2, +4} → 11	6	1, 2, 4, (5, 7 \| 5, 9 \| 6, 7 \| 6, 10 \| 8, 9 \| 8, 10), 11

In der Tabelle rechts sind die 15 Ketten der Länge 5 für die Zahl 11 als vier Muster mit Alternativen für Teilketten dargestellt. In der ersten Zeile stehen beispielsweise die Ketten, die mit 1, 2, 3, 4 beginnen. An dieser Stelle fehlt noch 11–4 = 7, was in zwei Schritten nur mit einem Schritt von 3 und einem von 4 erreicht werden kann, auf deren Reihenfolge es aber nicht ankommt; das sorgt für die beiden Varianten zwischen 4 und 11. In der letzten Zeile fehlen zwischen 4 und 11 noch drei Schritte mit den Schrittweiten 1, 2 und 4, was in sechs verschiedenen möglichen Reihenfolgen geschehen kann. Nicht in den Varianten können solche Zahlen landen, die später noch als Schrittweiten gebraucht werden. Bei einer Suche durch alle Ketten braucht man also nur 4 verschiedene Muster statt 15 verschiedene Einzelketten zu betrachten, da sich die Ketten eines Musters solange gleich verhalten, bis eine der Zahlen aus den Varianten als Schrittweite gebraucht wird.

Heuristische Verfahren

Ein heuristische Verfahren ist eines, mit dem mit relativ wenig Aufwand eine kurze Additionskette für eine Zahl n gefunden werden kann, von der man aber nicht weiß, ob sie eine kürzeste für n ist. Das kann für folgende Zwecke nützlich sein:

Ist ℓ(n) bekannt und liefert das Verfahren eine Kette der Länge ℓ(n), so hat man eine kürzeste.
Liefert das Verfahren eine Kette der Länge r für n, so ist r eine obere Schranke für ℓ(n). Das kann man nutzen, um beim Suchen nach Ketten kleinerer Länge diejenigen angefangenen Ketten nicht mehr betrachten zu müssen, die sich keinesfalls mehr zu einer Kette einer Länge <r ergänzen lassen.
Wenn es nur um die Optimierung einer Potenzierung geht, ist eine fast optimale Lösung meistens ausreichend.

Teilung der Binärdarstellung

$\overbrace {\underbrace {111111} _{63}\underbrace {0101011} _{43}} ^{8107}\qquad \overbrace {\underbrace {10\dotso {}0} _{2^{k-5}}\underbrace {11101} _{29}} ^{2^{k}+29}=\overbrace {\underbrace {10\dotso {}011} _{2^{k-3}+3}\underbrace {101} _{5}} ^{2^{k}+29}\qquad \overbrace {\underbrace {1001111011} _{635}\underbrace {01001111011} _{635}} ^{1301115}$

Im ersten Beispiel wird eine Additionskette für die 8107 gesucht, deren Binärdarstellung vorne dieselbe Ziffernfolge wie die 63 und hinten wie die 43 enthält. Hat man nun eine Additionskette für 63, in der 43 vorkommt, nämlich (1, 2, 3, 5, 10, 20, 40, 43, 63), so lässt diese sich zu einer Kette der Länge 16 für 8107 erweitern: (…, 2·63, …, 2⁷·63, 8107 = 2⁷·63+43).

Im zweiten Beispiel geht es um Additionsketten für alle $2^{k}+29$ . Hier verwendet man eine Additionskette für $2^{k-3}+3$ , in der 5 vorkommt, nämlich (1, 2, 3, 5, 8, …, 2^k–3, 2^k–3+3, 2^k–2+6, 2^k–1+12, 2^k+24, 2^k+29).

Faktormethode (1)

Hat ein a eine Additionskette der Länge r und b eine der Länge s, so hat a·b eine der Länge r+s, nämlich die Kette für a gefolgt von der für b, wobei jedes Kettenglied der zweiten Kette mit a multipliziert ist. Alle Ketten für 15 in der oberen Tabelle haben diese Gestalt. Zuerst gibt es eine Kette für 3 oder 5, dann das 3-fache einer Kette für 5 bzw. das 5-fache einer Kette für 3.

Leider überträgt sich die Eigenschaft, eine kürzeste Kette zu sein, nicht von den Ketten der Faktoren auf die des Produkts. So ist ℓ(3) = 2 und ℓ(11) = 5, aber ℓ(33) = 6 < ℓ(3)+ℓ(5). Für ein Produkt a·b können drei Fälle auftreten:

ℓ(a·b) = ℓ(a)+ℓ(b) und alle kürzesten Ketten für a·b sind Produkt zweier Ketten für a und für b. Beispiele: a=3, b=5 mit (1, 2, 3, 6, 9, 15) oder a=5, b=97, ℓ(5)=3, ℓ(97)=8 mit (1, 2, 4, 5, 10, 20, 40, 60, 120, 240, 245, 485).
ℓ(a·b) = ℓ(a)+ℓ(b) mit weiteren Ketten der Länge ℓ(a)+ℓ(b). Beispiel: a=3, b=23, ℓ(3)=2, ℓ(23)=6 mit einer kürzesten Kette (1, 2, 4, 8, 16, 17, 34, 35, 69), die keine Vielfachen von 3 oder 23 enthält.
ℓ(a·b) < ℓ(a)+ℓ(b). Beispiel: a=17, b=19, ℓ(17)=5, ℓ(19)=6, jedoch ℓ(323)=10 mit einer kürzesten Kette (1, 2, 3, 5, 10, 20, 40, 80, 160, 320, 323).

Faktormethode (2)