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 = a0 < a1 < ... < ak = n of integers such that every al(l \geq 1) can be written as the sum ai+aj 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 limn ––> 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 al 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