If you are serious about the problem, you may not try to find a solution with the lowest number of multiplications, but with the lowest execution time.
Consider a model where you can start a multiplication in every cycle, but each multiplication takes a fixed number of cycles, say 3 cycles. A method calculating x^n with k multiplications might take 3k cycles (if each multiplication depends on a result that was calculated just before), while a a method using more multiplications might run quicker.
For example: To calculate x^15, you might calculate in that order x^2 = x*x, x^3 = (x^2)*x, x^6 = (x^3)^2, x^7 = x^6 * x, x^14 = (x^7)^2, x^15 = x^14 * x. Six multiplications, but each dependent on the previous one.
Or you calculate x^2, x^4 = (x^2)^2, x^3 = x^2 * x, x^5 = (x^4)*x, x^15 = x^5 * x^3, so you have only four multiplications depending on previous results.