Algorithm for calculating $A^n$ with as few multiplications as possible Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $A^n$ in a structure where multiplication is associative?

For example, suppose $A$ is a square matrix. Matrix multiplication is associative, and I can compute $A^9$ with $4$ multiplications:

$$A^2 = A \cdot A$$

$$A^3 = A^2 \cdot A$$

$$ A^6 = A^3  \cdot A^3 $$
$$ A^9 = A^6 \cdot A^3 $$

One method which works is to compute $A^{2^i}$ and use the binary representation of $n$, but this is not always optimal, e.g. with $n=23$, we can do it in $6$ multiplications:

$$ A^2 = A \cdot A $$

$$ A^3 = A^2 \cdot A $$

$$ A^5 = A^3 \cdot A^2 $$

$$ A^{10} = A^5 \cdot A^5 $$

$$ A^{20} = A^{10} \cdot A^{10} $$

$$ A^{23} = A^{20} \cdot A^3 $$

rather than $7$:

$$ A^2 = A\cdot A $$
$$ A^4 = A^2 \cdot A^2 $$
$$ A^8 = A^4 \cdot A^4 $$
$$ A^{16} = A^8 \cdot A^8 $$
$$ A^{20} = A^{16} \cdot A^4 $$
$$ A^{22} = A^{20} \cdot A^2 $$
$$ A^{23} = A^{22} \cdot A $$

Is there an algorithm which gives the quickest way?
There seems to be no efficient algorithm for this. Quoting Wikipedia on Addition-chain exponentiation:


  … the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: 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.  Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.


On the same page, however, it does link to a reference* of some methods better than binary exponentiation.

One simple example is to use base-N number instead of base-2. e.g. for A510,

with binary:   2 = 1 + 1
               3 = 2 + 1
               6 = 3 + 3
               7 = 6 + 1
              14 = 7 + 7
              15 = 14 + 1
              30 = 15 + 15
              31 = 30 + 1
              62 = 31 + 31
              63 = 62 + 1
             126 = 63 + 63
             127 = 126 + 1
             254 = 127 + 127
             255 = 254 + 1
             510 = 255 + 255   (15 multiplications)

with base-8:   2 = 1 + 1
               3 = 2 + 1
               4 = 3 + 1
               5 = 4 + 1
               6 = 5 + 1
               7 = 6 + 1
              14 = 7 + 7
              28 = 14 + 14
              56 = 28 + 28
              63 = 56 + 7
             126 = 63 + 63
             252 = 126 + 126
             504 = 252 + 252
             510 = 504 + 6      (14 multiplications)

with base-4:   2 = 1 + 1
               3 = 2 + 1
               4 = 2 + 2
               7 = 4 + 3
              14 = 7 + 7
              28 = 14 + 14
              31 = 28 + 3
              62 = 31 + 31
             124 = 62 + 62
             127 = 124 + 3
             254 = 127 + 127
             508 = 254 + 254
             510 = 508 + 2      (13 multiplications)


(I don't know how to choose the optimal N.)

*: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), pp 129–146
[Edited:This is about solving the Project Euler problem, and not directly about your 
question. ] Admittedly, I'm quite late but remember having worked out this problem myself. The quickest cut to the solution is to use this  OEIS page . 

Add up the right hand entries for the first 200 rows, and you're done.As a general hint to Project Euler problems, when all this much theory is required, avoid writing your own programs and look it up somewhere.