# zbMATH — the first resource for mathematics

Remarks on number theory. III: On addition chains. (English) Zbl 0219.10064
[Part II, Acta arithmetica 5, 171-177 (1959; Zbl 0092.04601)]
An addition chain is a sequence $$1 = a_0 < a_1 < \ldots <a_k = n$$ of integers such that every $$a_l(l \geq 1)$$ can be written as the sum $$a_i+a_j$$ of two preceding members of the sequence. Define $$l(n)$$ to be the smallest $$k$$ for which such a sequence exists. A.Brauer [Bull. Am. Math. Soc. 45, 736-739 (1939; Zbl 0022.11106)] has shown that $$\lim_{n \to \infty} l(n) \log 2/\log n=1$$ and that, for all $$n$$, $l(n) < {\log n \over \log 2}+{\log n \over \log \log n}+O\left({\log n \over \log\log n} \right). \tag{1}$ The present author now shows that (1) holds with equality for almost all $$n$$. The methods of proof are typically Erdős. The generalisation to the case where each $$a_l$$ can be written as the sum of at most $$r(\geq 2)$$ preceding members of the sequence is briefly dealt with, and similar results are stated.
Reviewer: I.Anderson

##### MSC:
 11B75 Other combinatorial number theory 11B83 Special sequences and polynomials
Full Text: