1
$\begingroup$

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.

  • 1
    Have you looked at the references in http://oeis.org/A003313? This looks related to the http://mathworld.wolfram.com/ScholzConjecture.html2011-10-13

2 Answers 2

0

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).$

-1

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 ?

  • 0
    Really, I have no idea. And I still don't see the relation between your question and mine.2011-10-13