I think the smallest primitive but non-minimal addition chain is the Fibonacci numbers to 8: 1,2,3,5,8. As for Hansen chains, Knuth describes them as addition chains where certain elements are underlined. Each term in the chain is the sum of the most recent underlined term and some other term. So, for example, you couldn't (in general) do something like: ..., a, b, 2a, 2b, ... In order to get the 2a term, b can't be underlined, but then the next term must use either a, or (if it is underlined) 2a as an addend; b+b is out of bounds. (I say in general, because if 2a-b or 2b-2a is an earlier term in the sequence the underlining could be done differently.) As far as I know, it is still an outstanding conjecture that there is always a minimal addition chain for n that is a Hansen chain. Franklin T. Adams-Watters -----Original Message----- From: David Wilson <davidwwilson@comcast.net> I know a lot of work has been done on minimal addition chains (shortest in number of additions). Presumably this is because minimal addition chains are of interest in optimizing certain operations, e.g, computing powers of large matrices or other complicated objects. I was curious if anyone has explored the idea of primitive addition chains, in which every element is necessary, that is, removing any element but the last does not yield an addition chain. It is easy to show that all minimal addition chains are primitive. But not all primitive chains are minimal (I state this without proof, I know it to be true, it requires only exhibiting a non-minimal primitive addition chain for some n). For n >= 4, the complete addition chain for n, (1,2,3,...,n), is not primitive, because the element n-1 may be removed yielding an addition chain. So what would be the smallest n for which some primitive addition chain for n is longer than a minimal chain for n? For small n, what is the length of the longest primitive addition chain for n? I would also like to know what Hansen chains are. The Mathworld description was not particularly enlightening to me, and there was very little information on the Web. An example with explanation might help me. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com