A CONJECTURE IN ADDITION CHAINS RELATED TO SCHOLZ CONJECTURE

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 addi tion chains is Scholz's 1937 conjecture that for all natural numbers n , l(2n - 1) less-than-or-equal-to 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 conjec ture, namely, that for each integer n greater-than-or-equal-to 1 there exists an addition chain for 2n - 1 whose length equals l(n) + n - 1 . Obviously, our conjecture implies (and is stronger than) Scholtz's c onjecture. However, it is not as bold as conjecturing that l(2n - 1) = l(n) + n - 1 , which is known to hold, so far, for only the twenty-on e values of n which were obtained by Knuth and Thurber after extensive computations. By utilizing a series of algorithms we establish our co njecture for all n < 128 by actually computing the desired addition ch ains. We also show that our conjecture holds for infinitely many n , f or example, for all n which are powers of 2.