2

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?

Tobl
  • 123

2 Answers2

5

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

user7530
  • 49,280
3

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

Mark Bennet
  • 100,194
  • Thanks. I'm guessing the number of possibilities can be generalized as: For a largest common factor that itself has a prime factorization of p1^e1 * p2^e2 * ... * pn^en there are (p1+1) * (p2+1) * ... * (pn+1) ways to arrange those factors on the inner or outer exponent? – Tobl Nov 13 '17 at 21:11
  • 1
    @Tobl you probably mean $(e_1+1)\dots$ for the factorisation of the $d$ I mention. – Mark Bennet Nov 13 '17 at 21:19
  • 1
    yes, right, those should all be ei, not pi. I don't think comments can be edited? – Tobl Nov 13 '17 at 21:40
  • @Tobl If what I said is helpful, that is enough – Mark Bennet Nov 13 '17 at 21:42