Remarks on number theory. III: On addition chains. (English) Zbl 0219.10064

Erdős, Paul

Acta Arith. 6, 77-81 (1960).

[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

Citations:

Zbl 0092.046; Zbl 0092.04601; Zbl 0022.11106