Calculating optimal addition chains (Q644848)

An addition chain for a natural number \(n\) is a sequence \(1=a_0 < a_1 < \cdots < a_r =n\) of integers such that for each \(0 < i \leq r\), \(a_i = a_j+a_k\) for some \(0\leq k \leq j <i\). The minimal length of an addition chain for \(n\) is denoted by \(\ell(n)\) and such a chain of length \(\ell(n)\) is called \textit{optimal}. The author presents a new algorithm for calculating optimal chains. When used for a single value \(n\) this algorithm is slower than the best known present ones but it is faster when used to calculate a range of optimal addition chains. Using this new algorithm the author computed the values of \(\ell(n)\) for \(n\leq 2^{32}\), this gives a disproof of the conjecture \(\ell(2n)\geq \ell(n)\). Moreover, exact equality in the Scholz-Brauer conjecture \(\ell(2^n-1)=\ell(n)+n-1\) has been confirmed for many new values.