Let $A$ be some object in a space with a notion of associative multiplication, eg., imagine that $A$ is a square matrix. Here is my question: given some set of positive integers $S=\{s_1,...,s_n\}$, how do we compute each of the powers $\{A^{s_1}, A^{s_2},...,A^{s_n}\}$ using the fewest possible number of multiplications?
For example, consider $S=\{2,3,6\}$. Then we need three multiplications in total:
A2 = A*A
A3 = A2*A
A6 = A3*A3
Note that this is more efficient than a naive binary expansion of the members of $S$, since we can bypass $A^4$. Having sorted $S$ in ascending order, I guess this problem can be reduced to the recursive step: what is the fewest number of multiplications required to produce $A^{s_n}$ given cached copies of $\{A^{s_1}, A^{s_2},...,A^{s_{n-1}}\}$? This problem seems related to the change making problem.
Note: I am most interested in an algorithm that tells me what to multiply with what.