AUFGABE 253

253. Eine Kette a_{0}, a_{1}, …, a_{r} natürlicher Zahlen, beginnend mit a_{0} = 1 und schließend mit a_{r} = n, heiße eine Additionskette der Zahl n, wenn für ρ > 0 jedes a_{ρ} = a_{σ} + a_{τ} (0 ≤ σ, τ < ρ) darstellbar ist. Für n = 666 ist z.B.

1, 2, 4, 8, 16, 24, 40, 80, 160, 320, 640, 664, 666

eine solche Kette mit r = 12, ebenso

1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 324, 648, 666.

(Immer muß a_{2} = 2 und a_{2} = 3 oder 4 sein.)

Das minimale l, für das es eine Additionskette a_{0}, a_{1}, …, a_{l} = n gibt, heiße die Länge l(n) von n. (Subtraktion sei nicht gestattet!)

Dann gelten folgende Abschätzungen:

m + 1 ≤ l(n) ≤ 2m für 2^{m} + 1 ≤ n ≤ 2^{m+1}, (1)

l(ab) ≤ l(a) + l(b). (2)

In (1) gilt für m > 2 sogar l(n) < 2m, nämlich speziell

l(2^{m+1} − 1) ≤ m + l(m). (3)

Dies läßt vermuten, daß sich (1) allgemein besser nach oben abschätzen läßt. Weitere Frage: Läßt sich die aus (1) folgende Abschätzung

(4) 1 ≤ lim sup_{n→∞} \frac{log 2}{log n} l(n) ≤ 2

mit einfachen Hilfsmitteln verbessern?

Anwendungsmöglichkeit: Es soll die n-te Potenz eines Kongruenzrestes mit möglichst wenig Multiplikationen gebildet werden. Man kann dann ohne Multiplikationstabelle immer mit l(n) Multiplikationen auskommen.

Kiel. Arnold Scholz.

(Eingegangen am 29. 6. 1937.)