Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 $ l(n)$ 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 $ n,l({2^n} - 1) \leq l(n) + n - 1$. 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 $ n \geq 1$ there exists an addition chain for $ {2^n} - 1$ whose length equals $ l(n) + n - 1$. Obviously, our conjecture implies (and is stronger than) Scholtz's conjecture. However, it is not as bold as conjecturing that $ l({2^n} - 1) = l(n) + n - 1$, 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 $ n \leq 128$ 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.

References [Enhancements On Off] (What's this?)

  • [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 $ l(2n) = l(n)$ and $ l({2^n} - 1) = n + l(n) - 1$, 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)

Similar Articles

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

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

Additional Information

Keywords: Addition chain, Scholz conjecture, short chain
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society