Finding all expressions of a number as an exponentiation

Question

Is there a way to systematically determine all the ways a number can be expressed as an exponentiation of two natural numbers? For example,

64 = 64^1 = 8^2 = 4^3 = 2^6 

, but how would I determine this without brute-forcing through roots or logarithms?

Answer 1

If you are allowed to factorise the number, you would find the prime factorisation, and the highest common factor $d$ of all the exponents - any factor of $d$ works.

So in your example you get $2^6$.

$6=2^1\times 3^1$ and there will be $(1+1)\times (1+1)=4$ possibilities

Answer 2

"Brute-forcing through roots" is actually a fine strategy, though... you only need to check $a^{1/n}$ for $O(\log a)$ possible exponents $n$.

Of course there are complications involved in numerically extracting the $n$th root; these can be avoided by doing a binary search on integers $b$ to find a $b$ which minimizes $|b^n - a|$. This version of the algorithm will run in $O(\log a)^2$ time (since you will need $O(\log a)$ iterations of binary search).

Finally, you can of course factor $a$ and look at the prime exponents in the factorization. In terms of algorithmic complexity, this will be slower than the "brute force" solution, since there is no known factorization algorithm that runs in time polynomial in $\log a$.