Show how to compute $2^{343}$ using the least multiplication. Show how to compute $2^{343}$ using the least multiplication.

If you have $x$, you can calculate $x^7$ in four integer multiplications:


*

*$x \cdot x = x^2$

*$x^2 \cdot x^2 = x^4$

*$x^4 \cdot x^2 = x^6$

*$x^6 \cdot x = x^7$.


Since $343=7^3$, this means you can calculate $2^{343}$ in twelve multiplications: four to go from $2$ to $2^7$, four to go from $2^7$ to $(2^7)^7=2^{49}$, and four to go from $2^{49}$ to $(2^{49})^7=2^{343}$.
