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

*a*

_{0}<

*a*

_{1}<

*a*

_{2}< ⋯ <

*a*

_{r}=

*n*

where for each 0<*k*≤*r*, there are indices *i* and *j* such that

*a*

_{k}=

*a*

_{i}+

*a*

_{j}, 0 ≤

*i*≤

*j*<

*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:

^{q}-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.