what's new about powers ? A003313

[Antti Karttunen]

"David W. Wilson" wrote:

> Antti Karttunen wrote:
> > 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?

Yes, just make the summands of the addition chain the exponents of x,
and substitute *'s for +'s.

See: http://mathworld.wolfram.com/AdditionChain.html

and

http://mathworld.wolfram.com/ScholzConjecture.html

(Wohoo, I guess I won't get any work done today either.
Thanks Eric!)

Terveisin,

Antti