An addition chain of length r for a positive integer n is a sequence of integers

1 = a0 <  a1 <  a2 <  ⋯ <  ar = n

where for each 0<kr, there are indices i and j such that

ak = ai + aj ,  0 ≤ ij < k .

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:

ℓ(2q-1) ≤ q - 1 + ℓ(q) ,   1 ≤ q .

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.


References:
[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.

Links:
Shortest Addition Chains, from Achim Flammenkamp.