what's new about powers ? A003313

[David W. Wilson]

Antti Karttunen wrote:
> 
> Jud McCranie wrote:
> 
> > At 01:55 AM 11/2/2001 +0200, Antti Karttunen wrote:
> >
> > >Type a paragraph or two, or in this case, the specific multiplication
> > >algorithm from the book, to be included in the comments of A003313,
> >
> > The algorithm varies depending on n.  The book discusses the factor method,
> > the power tree method, and the binary method.  For n < 100000 the power
> > tree method is optimal but for a few cases the factor method is best.
> 
> Thanks.
> 
> Does this "optimality" refer to finding the optimal (i.e. in this case,
> the minimal) value of n, or finding what's that minimum value,
> in the optimal amount of time?
> 
> If what is meant is the former sentence, then could we have sequence
> for those n, for which the factor method is the best (or better than
> the power tree method)?
> 
> Here's again the sequence, if somebody forgot from which sequence we are
> talking about:
> 
> ID Number: A003313 (Formerly M0255)
> Sequence:  0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,
>            7,5,6,6,7,6,7,7,7,6,7,7,7,7,7,7,8,6,7,7,7,7,8,7,8,7,8,8,8,7,
>            8,8,8,6,7,7,8,7,8,8
> Name:      Minimum multiplications to compute n-th power.
> References D. E. Knuth, The Art of Computer Programming. Addison-Wesley,
>               Reading, MA, Vol. 2, p. 446.
> Keywords:  nonn
> Offset:    1
> Author(s): njas

Isn't A003313(n) the same as the number of additions in the shortest
addition chain for n?  If not, how does it differ?