A conjecture in addition chains related to Scholz's conjecture
Authors:
Walter Aiello and M. V. Subbarao
Journal:
Math. Comp. 61 (1993), 1723, S1
MSC:
Primary 11B83; Secondary 11Y55
MathSciNet review:
1189515
Fulltext 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 twentyone 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
(1,40a), http://dx.doi.org/10.1090/S000299041939070687
 [2]
A.
A. Gioia, M.
V. Subba Rao, and M.
Sugunamma, The ScholzBrauer problem in addition chains, Duke
Math. J. 29 (1962), 481–487. MR 0140478
(25 #3898)
 [3]
Walter
Hansen, Zum ScholzBrauerschen Problem, J. Reine Angew. Math.
202 (1959), 129–136 (German). MR 0138584
(25 #2027)
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 1: Fundamental
algorithms, Second printing, AddisonWesley Publishing Co., Reading,
Mass.LondonDon Mills, Ont, 1969. 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), 4142.
 [7]
Kenneth
B. Stolarsky, A lower bound for the ScholzBrauer problem,
Canad. J. Math. 21 (1969), 675–683. MR 0246845
(40 #114)
 [8]
Edward
G. Thurber, Addition chains and solutions of
𝑙(2𝑛)=𝑙(𝑛) and
𝑙(2ⁿ1)=𝑛+𝑙(𝑛)1., Discrete
Math. 16 (1976), no. 3, 279–289. MR 0432583
(55 #5570)
 [9]
W.
R. Utz, A note on the ScholzBrauer problem in
addition chains, Proc. Amer. Math. Soc. 4 (1953), 462–463.
MR
0054618 (14,949e), http://dx.doi.org/10.1090/S0002993919530054618X
 [1]
 A. T. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736739. MR 0000245 (1:40a)
 [2]
 A. A. Gioia, M. V. Subbarao, and M. Sugunamma, The ScholzBrauer problem in addition chains, Duke Math. J. 29 (1962), 481487. See also A. A. Gioia and M. V. Subbarao, The ScholzBrauer problem in addition chains. II, Proc. Eighth Manitoba Conf. on Numerical Math. and Computing, 1978, pp. 174251. MR 0140478 (25:3898)
 [3]
 W. Hansen, Zum ScholzBrauerschen problem, J. Reine Angew. Math. 202 (1959), 129136. MR 0138584 (25:2027)
 [4]
 D. E. Knuth, The art of computer programming, 2nd ed., AddisonWesley, Reading, Mass., 1969, pp. 398422. (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), 4142.
 [7]
 K. B. Stolarsky, A lower bound for the ScholzBrauer problem, Canad. J. Math. 21 (1969), 675683. MR 0246845 (40:114)
 [8]
 E. G. Thurber, Additional chains and solutions of and , Discrete Math. 16 (1976), 279289. MR 0432583 (55:5570)
 [9]
 W. R. Utz, A note on the ScholzBrauer problem in addition chains, Proc. Amer. Math. Soc. 4 (1953), 462463. 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
DOI:
http://dx.doi.org/10.1090/S00255718199311895153
PII:
S 00255718(1993)11895153
Keywords:
Addition chain,
Scholz conjecture,
short chain
Article copyright:
© Copyright 1993
American Mathematical Society
