Vol. 49, No. 1, 1973

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
 
Other MSP Journals
The Scholz-Brauer problem on addition chains

Edward G. Thurber

Vol. 49 (1973), No. 1, 229–242
Abstract

An addition chain for a positive integer n is a set 1 = a0 < a1 < < ar = n of integers such that every element ai is the sum aj + ak of two preceding members (not necessarily distinct) of the set. The smallest length r for which an addition chain for n exists is denoted by l(n). Let λ(n) = [log 2n], and let ν(n) denote the number of ones in the binary representation of n. The purpose of this paper is to show how to establish the result that if ν(n) 9 then l(n) λ(n) + 4. This is the m = 3 case of the conjecture that if ν(n) 2m + 1 then l(n) λ(n) + m + 1 for which cases m = 0,1,2 have previously been estabished. The fact that the conjecture is true for m = 3 leads to the theorem that n = 2m(23) + 7 for m 5 is an infinite class of integers for which l(2n) = l(n). The paper concludes with this result.

Mathematical Subject Classification
Primary: 10L15
Milestones
Received: 1 January 1972
Published: 1 November 1973
Authors
Edward G. Thurber