On addition chains. (Q2590627)

Additionskette für \(n\) heißt eine natürliche Zahlenfolge \[ a_0=1<a_1<a_2\cdots<a_r=n, \] wenn jedes Kettenglied \(a_\varrho=a_\sigma+a_\tau\) mit \(\sigma,\tau<\varrho\) darstellbar ist, spezielle Additionskette, wenn dabei \(\sigma=\varrho-1\) ist. Die kleinstmögliche Gliederzahl \(r\) für ein \(n\) heißt die Länge \(l(n)\) von \(n\) und \(l^*(n)\) die für spezielle Additionsketten. Wie Ref. als Aufgabe stellte (Jber. Deutsche Math. Verein. 47 (1937), 41 kursiv), zeigt Verf. \[ l(ab)\leqq l(a)+l(b);\qquad m<l(n)\leqq 2m\quad\text{für}\quad 2^m<n\leqq 2^{m+1}. \] Ferner \(l(2^{m+1}-1)\leqq m+l^*(m+1)\) und damit oben \(l(n)<2m\) für \(n\geqq 8\). Nach der zweiten Ungleichung liegt der \(\limsup\left(l(n):\dfrac{\log n}{\log2} \right)\) zwischen 1 und 2. Verf. beweist nun, daß er eins ist, daß nämlich für \(n\geqq 3\) \[ l(n)<\frac{\log n}{\log 2}\left(1+\frac1{\log\log n}+\frac{2\log 2} {(\log n)^{1-\log2}}\right) \] Dies liefert bei \(n=a\cdot 2^r+b\) mit \(r=[\log\log n]+1\) die \(b\leqq 2^{r-1} \leqq a\) aufweisende Kette \[ 1,2,3,4,\dots,a-1,a,2a,4a,\dots,2^{r-1}a,2^ra,2^ra+b. \]