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  conjectured in 1937 that:

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

Two years later, Brauer  showed that the conjecture is true for special addition chains called star chains. Utz  proved that the conjecture holds for q such that ν(q) ≤ 2. Gioia, Subbarao, and Sugunamma  proved that it holds for q such that ν(q) ≤ 3. Bahig and Nakamula  proved that it holds for all q such that ν(q) ≤ 5. See Knuth  for an extensive and entertaining survey on computing addition chains.

References:
 A. Scholz, Aufgabe 253, Jber. Deutsch. Math.-Verein. 47 (1937), 41.
 A. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736–739.
 W. R. Utz, A note on the Scholz—Brauer problem in addition chains, Proc. Amer. Math. Soc. 4 (1953), 462–463.
 A. A. Gioia, M.-V. Subbarao, and M. Sugunamma, The Scholz—Brauer problem in addition chains, Duke Math. J. 29 (1962), 481–487.
 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.
 D. E. Knuth, The Art of Computer Programming, volume 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 2003, p. 465–485.