Star reduction among minimal length addition chains (Q644852)

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)\). If the above integer \(j=i-1\), the step \(i\) is called a \textit{star step}. It is known that there is a minimal length addition chain for \(n\) such that the last four steps are star steps. The author conjectures that this even true that there is a minimal length addition chain for \(n\) such that the last \(\lfloor \ell(n)/2 \rfloor\) steps are star steps and he verified that this holds for \(n\leq 2^{18}\). An application of this conjecture leads to significant progress for the cost of computing a minimal addition chain for \(n\).