A conjecture in addition chains related to Scholz’s conjecture
HTML articles powered by AMS MathViewer
- by Walter Aiello and M. V. Subbarao PDF
- Math. Comp. 61 (1993), 17-23 Request permission
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
- Alfred Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736–739. MR 245, DOI 10.1090/S0002-9904-1939-07068-7
- 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 140478, DOI 10.1215/S0012-7094-62-02948-4
- Walter Hansen, Zum Scholz-Brauerschen Problem, J. Reine Angew. Math. 202 (1959), 129–136 (German). MR 138584, DOI 10.1515/crll.1959.202.129
- Donald E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. Second printing. MR 0286317 D. H. Lehmer, See problem number 13 on page 421 of Knuth, where this problem is outlined. A. Scholz, Jahresbericht, Deutsche Mathematiker Vereinigung, Aufgabe 252, 47 (1937), 41-42.
- Kenneth B. Stolarsky, A lower bound for the Scholz-Brauer problem, Canadian J. Math. 21 (1969), 675–683. MR 246845, DOI 10.4153/CJM-1969-077-x
- Edward G. Thurber, Addition chains and solutions of $l(2n)=l(n)$ and $l(2^{n}-1)=n+l(n)-1.$, Discrete Math. 16 (1976), no. 3, 279–289. MR 432583, DOI 10.1016/0012-365X(76)90105-9
- W. R. Utz, A note on the Scholz-Brauer problem in addition chains, Proc. Amer. Math. Soc. 4 (1953), 462–463. MR 54618, DOI 10.1090/S0002-9939-1953-0054618-X
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 17-23
- MSC: Primary 11B83; Secondary 11Y55
- DOI: https://doi.org/10.1090/S0025-5718-1993-1189515-3
- MathSciNet review: 1189515