An addition chain of length r for a positive integer n is a sequence of integers
where for each 0<k≤r, there are indices i and j such that
By ℓ(n), one means the smallest r for which there an addition chain for n exists. For instance, one easily verifies: ℓ(1) = 0, ℓ(2) = 1, ℓ(3) = ℓ(4) = 2.
Scholz [1] conjectured in 1937 that:
Two years later, Brauer [2] showed that the conjecture is true for special addition chains called star chains. Utz [3] proved that the conjecture holds for q such that ν(q) ≤ 2. Gioia, Subbarao, and Sugunamma [4] proved that it holds for q such that ν(q) ≤ 3. Bahig and Nakamula [5] proved that it holds for all q such that ν(q) ≤ 5. See Knuth [6] for an extensive and entertaining survey on computing addition chains.
[1] A. Scholz, Aufgabe 253, Jber. Deutsch. Math.-Verein. 47 (1937), 41.
[2] A. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736–739.
[3] W. R. Utz, A note on the Scholz—Brauer problem in addition chains, Proc. Amer. Math. Soc. 4 (1953), 462–463.
[4] A. A. Gioia, M.-V. Subbarao, and M. Sugunamma, The Scholz—Brauer problem in addition chains, Duke Math. J. 29 (1962), 481–487.
[5] H. M. Bahig and K. Nakamula, Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True, J. Algorithms 42 (2002), 304–316.
[6] D. E. Knuth, The Art of Computer Programming, volume 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 2003, p. 465–485.