Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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/S0025-5718-1993-1189515-3
PII: S 0025-5718(1993)1189515-3
Keywords: Addition chain, Scholz conjecture, short chain
Article copyright: © Copyright 1993 American Mathematical Society