Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the related Wikipedia article only provides methods to calculate relatively short chains but not the optimal chain.

1- What methods exist that can find the optimal addition chain for a given $n$?

2- How fast are these methods and how well do they scale with $n$?

3- Do methods exist that will only calculate the length of the optimal chain and could they be faster than ordinary methods?

4- Could a function that relates to addition chains be recursive?

share|cite|improve this question
I seem to remember that there is discussion of this topic in Volume 2 of Knuth The Art of Computer Programming, in connection with finding the optimal sequence of multiplications for calculating $x^n$ for given integer $n$. – MJD Sep 19 '12 at 14:23
The wikipedia page provides a reference where NP-completeness is claimed proven. – Sasha Sep 19 '12 at 16:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.