Show that you can calculate x ^ 62 using only 8 multiplications

Question

I have this method:

power (x, n) {  
    if n == 0
        return 1 
    if n is even
        return power(x * x, n/2)  
    if n is odd    
        return power(x * x, n/2) * x

I thought to calculate x ^ 64, which can be done using 6 multiplication actions, and then get x ^ 62 from there, but here I stuck. We can achieve it only by dividing by x and then again by x and not multiplying. Any idea of how to solve it or maybe another approach?

Answer 1

I don't know anything about programming. So I'm not sure what you are looking for. But you can calculate $x^{62} $ using $8$ multiplication as follows : $$x^2\to x^4\to x^6\to x^{12}\to x^{24}\to x^{30}\to x^{31}\to x^{62}. $$

Answer 2

Here are $8$ more solutions using $8$ multiplications:

$2,3,6,12,24,48,14,62$.

$2,4,6,12,24,48,14,62$.

$2,4,8,12,24,48,14,62$.

$2,3,5,10,20,40,22,62$.

$2,4,5,10,20,40,22,62$.

$2,4,8,10,20,40,22,62$.

$2,4,8,16,20,40,22,62$.

$2,3,5,10,11,20,31,62$.

I don't see any obvious way to determine an optimal solution, nor an easy way to prove that there is none using $7$ multiplications.