A new strategy for generating shortest addition sequences (Q644844)

The addition chain problem is to find the minimal length addition chain for a positive integer \(n\). Recall that an addition chain for \(n\) is a strictly increasing sequence of natural numbers \(1 =a_0, a_1, \dots, a_r =n\) such that for each \(0< i \leq r\), \( a_i = a_j +a_k\) for some \( 0 \leq k \leq j <i\) and \(r\) is the length of the addition chain. An addition sequence problem is, given a set of numbers \(X=\{ n_1, n_2,\dots,n_m\}\), to find the minimal number of additions needed to compute all \(m\) numbers starting from 1, which generalizes the addition chain problem. This problem is known to be NP-complete. The authors develop an algorithm to compute minimal length addition sequences using branch and bounding techniques to improve the computing time. The proofs of the validity of the bounding techniques are similar to the bounding techniques that have been previously developed when computing a minimal length addition chain for \(n\). The paper contains an implementation section reporting numerical experiments. It also includes 21 references.