6
$\begingroup$

I was looking at the nice puzzle Find $n^{23}$ with the least multiplication. My first instinct for this would have been to find $n^{2^i}$ for each $i$ first and then multiply these together as necessary to get $n^{23}$. This basic algorithm will always work for any integer power of $n$, since we can write $k$ in base 2 (i.e. as a sum of powers of 2) to get $n^k$ as a product of $n^{2^i}$ terms.

However, it's clearly not optimal in all cases. For $n^{23}$, this method would involve seven multiplications (one each to get $n^2,n^4,n^8,n^{16}$, then three for $n^{16}\times n^4\times n^2\times n$), whereas Kalaivanan showed that it can be done in six multiplications. Presumably this six-part solution is a case of some more general algorithm which will work for any $n^k$, but I'm struggling to see what that algorithm would be, and can't really see the motivation/inspiration which led to Kalaivanan's solution.

What is the least number of multiplications, in terms of $k\in\mathbb{N}$, to find $n^k$ given a general $n$?

$\endgroup$
  • 1
    $\begingroup$ Just a small comment. Wouldn't the problem sound a bit easier if stated. Find k through a set of additions starting from 1? Isn't this equivalent or am I missing something. $\endgroup$ – Marius Aug 28 '17 at 13:15
  • $\begingroup$ @Marius Hmm, I suppose it is equivalent. But realising that is an interesting and non-obvious part of the solution in itself, so I'd rather not include it in the problem statement. $\endgroup$ – Rand al'Thor Aug 28 '17 at 13:21
  • $\begingroup$ should I delete the comment above then? $\endgroup$ – Marius Aug 28 '17 at 13:22
  • $\begingroup$ @wl As a sequence of numbers, yes, but not as a general algorithm/formula in terms of $k$, which is what I was hoping for. $\endgroup$ – Rand al'Thor Aug 28 '17 at 13:33
9
$\begingroup$

To quote from the wikipedia page about Addition Chain Exponentiation:

On the other hand, the determination of a shortest addition chain is hard: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete.

There is no simple algorithm for it, apart from essentially trying out all ways of splitting it up into smaller parts. The tricky bit lies in the fact that if you try to split the calculation of $x^n$ into two separate calculations $x^a$ and $x^b$ with $a+b=n$, then it is not the case that the two sub-problems $x^a$ and $x^b$ are independent. Intermediate results from one of them can be used in the other to shorten the number of multiplications you need.

There's also a Project Euler problem that specifically asks you to calculate them.
Unsurprisingly, the sequence can be found in the OEIS as well.

$\endgroup$
  • $\begingroup$ Aww. That's a shame. (And it demonstrates the risk of posing a puzzle without knowing the answer!) $\endgroup$ – Rand al'Thor Aug 28 '17 at 13:32
  • $\begingroup$ @Jaapscherphuis you are so informative! To be honest, i did not know there was such a thing even while asking this in the first place. Glad to know it! $\endgroup$ – Oray Aug 28 '17 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.