Proof of a lower bound $\lambda(n)$ of the smallest number of multiplications $\ell(n)$ needed to compute $a^n$ for an integer $a$ Let $\ell(n)$ be the smallest number of multiplications needed to compute $a^n$ for any integer $a$. Here, a multiplication is $a_i := a_j \cdot a_k$ for $j, k &lt; i$ and $a_0 := a$, e.g. $\ell(8) = 3$. I want to show the following inequality:

$$\lambda(n) \leq \ell(n) \leq \lambda(n) + v(n) + 1,$$

where $\lambda(n)$ is one less than the number of significant bits of $n$ in the binary representation and $v(n)$ is the number of $1$s in the binary representation of $n$.

I tried to prove this inequality using induction and the upper bound for $\ell(n)$ is quite easy to show, however I don't see how I can prove the lower bound. The only thing about $\ell(n+1)$ I know is that it is less or equal to $\ell(n) + 1$. But if we for example look at $n=7$, we see that $\ell(n+1) &lt; \ell(n)$, so $\ell(n)$ is not monotonically increasing... Can anyone give me a hint how to show the lower bound or how $\ell(n)$ is bounded?

Thanks for any help in advance.
For the lower bound, we argue by induction that $a_i \leq a^{2^i}$ for all $i$. In order to get $a_t = n$, we must have $a^{2^t} \geq a_t = a^n$ or $2^t \geq n$. It follows that
$$t \geq \log n \geq \lfloor \log n \rfloor = \lambda(n).$$
Look at it the other way and try to put an upper bound on the exponents of the computable powers knowing the number of multiplications : for any given integer $k$, what is the greatest power of $a$ you can compute with only $k$ multiplications ?