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

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

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]**A. T. Brauer,*On addition chains*, Bull. Amer. Math. Soc.**45**(1939), 736-739. MR**0000245 (1:40a)****[2]**A. A. Gioia, M. V. Subbarao, and M. Sugunamma,*The Scholz-Brauer problem in addition chains*, Duke Math. J.**29**(1962), 481-487. See also A. A. Gioia and M. V. Subbarao,*The Scholz-Brauer problem in addition chains*. II, Proc. Eighth Manitoba Conf. on Numerical Math. and Computing, 1978, pp. 174-251. MR**0140478 (25:3898)****[3]**W. Hansen,*Zum Scholz-Brauerschen problem*, J. Reine Angew. Math.**202**(1959), 129-136. MR**0138584 (25:2027)****[4]**D. E. Knuth,*The art of computer programming*, 2nd ed., Addison-Wesley, Reading, Mass., 1969, pp. 398-422. (Second printing has some updates.) MR**0286317 (44:3530)****[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]**K. B. Stolarsky,*A lower bound for the Scholz-Brauer problem*, Canad. J. Math.**21**(1969), 675-683. MR**0246845 (40:114)****[8]**E. G. Thurber,*Additional chains and solutions of**and*, Discrete Math.**16**(1976), 279-289. MR**0432583 (55:5570)****[9]**W. R. Utz,*A note on the Scholz-Brauer problem in addition chains*, Proc. Amer. Math. Soc.**4**(1953), 462-463. MR**0054618 (14:949e)**

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