Vol. 49, No. 1, 1973

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 331: 1
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
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