Find a sequence of integer powers faster than the naive algorithm Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a_1^k,\ldots,a_n^k$ where $a_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a_i^k$ individually with the exponentiation by squaring. This takes a total of $O(n\log k)$ multiplications. 

Is this optimal? What if for each $a_i$, we have $\frac{1}{c} a_i \leq a_{i+1}\leq c a_i$.

I come up with this question because I was doing a binary search over $f(n)=n^k$.
In the worst case, this seems to be optimal. If your $a_i$ are pairwise coprime,
e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there 
may not be such a set; then, you powers share factors. You could exploit this
if you knew the shared factors for your $a_i$; but finding those is harder than
just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a_i$.