5
$\begingroup$

The question of finding the Minimal Addition Chain (MAC) for needed for Addition chain exponentiation seems to be NP-complete. As such, it would be nice to have a list for the small powers already computed. Wikipedia lists the MAC's for $n\le16$. I'm looking for the known MAC's for $n>16$.

  • 0
    @Srivatsan Agreed and updated, didn't even know about those tags!2012-04-03

2 Answers 2

4

See https://oeis.org/A003313 and references there, in particular the table up to n=10001.

3

This site about shortest addition chains lets you generate a shortest addition chain for any number < 2^27, and lists a lot of interesting properties and references about them.

  • 1
    Thanks @DaveBall. Note that the reference is also in the OEIS link provided by RobertIsrael.2012-04-12