It is sometimes also called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture, after Arnold Scholz who formulated it in 1937[1] and Alfred Brauer who studied it soon afterward and proved a weaker bound.
[2] Neill Clift has announced an example showing that the bound of the conjecture is not always tight.
Computing the length of the shortest addition chain that contains a given number x can be done by dynamic programming for small numbers, but it is not known whether it can be done in polynomial time measured as a function of the length of the binary representation of x. Scholz's conjecture, if true, would provide short addition chains for numbers x of a special form, the Mersenne numbers.
As an example, l(5) = 3: it has a shortest addition chain of length three, determined by the three sums Also, l(31) = 7: it has a shortest addition chain of length seven, determined by the seven sums Both l(31) and 5 − 1 + l(5) equal 7.
By using a combination of computer search techniques and mathematical characterizations of optimal addition chains, Clift (2011) showed that the conjecture is true for all n < 5784689.