Improved Generation of Minimal Addition Chains

An addition chain for a natural number n is a sequence 1=a ₀<a ₁< . . . <a _r =n of numbers such that for each 0<i≤r, a _i =a _j +a _k for some 0≤k≤j<i. An improvement by a factor of 2 in the generation of all minimal (or one) addition chains is achieved by finding sufficient conditions for star steps, computing what we will call nonstar lower bound in a minimal addition and omitting the sorting step.