ADDITION CHAINS - AN ERRATIC SEQUENCE

An addition chain for a positive integer n is a set 1 = a0 < a1 < ... < a(r) = n of integers such that for each i greater-than-or-equal-to 1 , a(i) = a(j)+ a(k) for some k less-than-or-equal-to j < i. This paper introduces the function NMC(n) which denotes the number of minimal ad dition chains for an integer n. The function is explicitly determined on certain classes of integers, and its relation to factor chains is e xplored. In particular the concept of a normal integer is introduced, and lower bounds for NMC(n) are developed for normal integers for whic h the factor chain method produces a minimal addition chain.