##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 219.10064

**Autor: ** Erdös, Paul

**Title: ** Remarks on number theory. III: On addition chains (In English)

**Source: ** Acta Arith. 6, 77-81 (1960).

**Review: ** [Part II, Acta arithmetica 5, 171-177 (1959; Zbl 092.04601)]

An addition chain is a sequence 1 = a_{0} < a_{1} < ... < 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 022.11106)] has shown that **lim**_{n ––> oo} 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**(**{log n \over log log n} **)**. (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

**Classif.: ** * 11B75 Combinatorial number theory

11B83 Special sequences of integers and polynomials

**Citations: ** Zbl 092.046

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag