A conjecture in addition chains related to Scholz's conjecture

Authors:
Walter Aiello and M. V. Subbarao

Journal:
Math. Comp. **61** (1993), 17-23, S1

MSC:
Primary 11B83; Secondary 11Y55

MathSciNet review:
1189515

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let denote, as usual, the length of a shortest addition chain for a given positive integer *n*. The most famous unsolved problem in addition chains is Scholz's 1937 conjecture that for all natural numbers . While this conjecture has been proved for certain classes of values of *n*, its validity for all *n* is yet an open problem. In this paper, we put forth a new conjecture, namely, that for each integer there exists an addition chain for whose length equals . Obviously, our conjecture implies (and is stronger than) Scholtz's conjecture. However, it is not as bold as conjecturing that , which is known to hold, so far, for only the twenty-one values of *n* which were obtained by Knuth and Thurber after extensive computations. By utilizing a series of algorithms we establish our conjecture for all by actually computing the desired addition chains. We also show that our conjecture holds for infinitely many *n*, for example, for all *n* which are powers of 2.

**[1]**Alfred Brauer,*On addition chains*, Bull. Amer. Math. Soc.**45**(1939), 736–739. MR**0000245**, 10.1090/S0002-9904-1939-07068-7**[2]**A. A. Gioia, M. V. Subba Rao, and M. Sugunamma,*The Scholz-Brauer problem in addition chains*, Duke Math. J.**29**(1962), 481–487. MR**0140478****[3]**Walter Hansen,*Zum Scholz-Brauerschen Problem*, J. Reine Angew. Math.**202**(1959), 129–136 (German). MR**0138584****[4]**Donald E. Knuth,*The art of computer programming. Vol. 1: Fundamental algorithms*, Second printing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR**0286317****[5]**D. H. Lehmer, See problem number 13 on page 421 of Knuth, where this problem is outlined.**[6]**A. Scholz,*Jahresbericht*, Deutsche Mathematiker Vereinigung, Aufgabe 252,**47**(1937), 41-42.**[7]**Kenneth B. Stolarsky,*A lower bound for the Scholz-Brauer problem*, Canad. J. Math.**21**(1969), 675–683. MR**0246845****[8]**Edward G. Thurber,*Addition chains and solutions of 𝑙(2𝑛)=𝑙(𝑛) and 𝑙(2ⁿ-1)=𝑛+𝑙(𝑛)-1.*, Discrete Math.**16**(1976), no. 3, 279–289. MR**0432583****[9]**W. R. Utz,*A note on the Scholz-Brauer problem in addition chains*, Proc. Amer. Math. Soc.**4**(1953), 462–463. MR**0054618**, 10.1090/S0002-9939-1953-0054618-X

Retrieve articles in *Mathematics of Computation*
with MSC:
11B83,
11Y55

Retrieve articles in all journals with MSC: 11B83, 11Y55

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1189515-3

Keywords:
Addition chain,
Scholz conjecture,
short chain

Article copyright:
© Copyright 1993
American Mathematical Society