Show how to compute $2^{343}$ using the least multiplication. Show how to compute $2^{343}$ using the least multiplication.
 A: We can get to $x^{343}$ in $11$ multiplication steps. 
Here is a path:
$$x^2,\quad x^3,\quad x^6,\quad x^{12},\quad x^{24},\quad x^{48},\quad x^{49},\quad x^{98},\quad x^{196},\quad x^{294},\quad x^{343}.$$
The procedure is similar to the one of mjqxxx. but gets to $x^{49}$ in $7$ steps instead of $8$. 
A: 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}$.
A: One way to do this (and probably the way the prof wants) is exponentiation by squaring. Note that $x^{2n} = (x^n)^2$ and $x^{2n + 1} = (x^n)^2 \cdot x$. We can either break down $343$ into smaller pieces this way, but it's easier to think about starting at the bottom:
$$
\begin{array}{ccc}
Value & Computation & Multiplications & Total Multiplications \\
2^2 & (2^1)^2 & 1 & 1 \\
2^5 & (2^2)^2 \cdot 2 & 2 & 3 \\
2^{10} & (2^5)^2 & 1 & 4 \\
2^{21} & (2^{10})^2 \cdot 2 & 2 & 6 \\
2^{42} & (2^{21})^2 & 1 & 7 \\
2^{85} & (2^{42})^2 \cdot 2 & 2 & 9 \\
2^{171} & (2^{85})^2 \cdot 2 & 2 & 11 \\
2^{343} & (2^{171})^2 \cdot 2 & 2 & 13 \\
\end{array}
$$
How did I pick these numbers? Look at the binary expansion of $343 = 101010111_2$. Starting at the second-left digit, for each $1$, square and multiply, and for each zero, just square. Note that each computation only uses $2$ and the previous computation, so you don't have to store any auxilary results. If you really wanted to, you could write $2^{343}$ as (this is what starting from the top looks like):
$$ \left( 2^{171} \right)^2 \cdot 2 $$
$$ \left( \left( 2^{85} \right)^2 \cdot 2 \right)^2 \cdot 2 $$
$$ \left( \left( \left(2^{42} \right)^2 \cdot 2 \right)^2 \cdot 2 \right)^2 \cdot 2 $$
$$\vdots$$
$$ \left( \left( \left( \left( \left( \left( \left( 2^2 \right)^2 \cdot 2 \right)^2 \right)^2 \cdot 2 \right)^2 \right)^2 \cdot 2 \right)^2 \cdot 2 \right)^2 \cdot 2 $$
Because we don't store any auxilary results, this method is one multiplication slower than mjqxxxx's method, but this one generalizes much more cleanly. Which you should use depends on if you want a general method or just speed (in which case, perhaps a lookup table is appropriate?)
