# 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 < 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) < \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.

-
Have you looked at the references in oeis.org/A003313? This looks related to the mathworld.wolfram.com/ScholzConjecture.html – Ross Millikan Oct 13 '11 at 17:19

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 ?
The answer to your question is $2^k$, but I don't see yet how this helps. Also, what exactly are "the computable exponents"? – Huy Oct 13 '11 at 17:42
well then, what does that say about $\ell(n)$ if $n > 2^k$ ? – mercio Oct 13 '11 at 17:46