Star reduction among minimal length addition chains (Q644852)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Star reduction among minimal length addition chains |
scientific article |
Statements
Star reduction among minimal length addition chains (English)
0 references
7 November 2011
0 references
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\).
0 references
addition chain
0 references
branch and bound algorithm
0 references
minimal length addition chain
0 references
star chain
0 references
0 references