Abstract
An addition sequence problem is given a set of numbers X = {n (1), n (2), . . . , n (m) }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n (j) , 1 a parts per thousand currency sign j a parts per thousand currency sign m, in the search tree.