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$?
