Algorithm to find whether a number X is an arbitrary power

Question

I basically need to have a function that finds that X is the result of a^b, and display a and b but I cannot use any available methods from math libraries.

Answer 1

Naive solution (pseudocode), looping over a (this is exponential time):

for (a = 2; a <= sqrt(X); ++a) {
    b = round ( log ( X ) / log( a ) )
    if (a^b == X) {
         output solution
         exit
    }
}
output no solution found

Better solution (pseudocode), looping over b (this is polynomial time):

for (b = 2; b <= log(X)/log(2); ++b) {
    a = round ( exp ( log(X)/b ) )
    if (a^b == X) {
         output solution
         exit
    }
}
output no solution found

Better solution in Python:

import math

def inv_power(x):
    upper_limit = math.log(x)/math.log(2)
    b = 2
    while b <= upper_limit:
        a = int(round( math.exp ( math.log(x)/b ) ) )
        if a**b == x:
            return a,b
        b = b + 1
    return None

Nice question. I'm disappointed so many people down voted it.

Answer 2

I assume integers (from comments) so without brute force I would try this:

1. use sieve of Eratosthenes O(X.log(log(X)))

   Up to sqrt(X) or half bits of X number 1<<(bits(X)>>1) to find primes you will be needing for this.

2. scan all found primes p(i) and check how many times you can divide X with it. m=~X/ln(X); O(m)

   Remember the number of divisions as n. If n<=1then ignore this prime p(i) and continue with next p(i+1). If n>1 then add the prime p(i) and its n to some list;

3. sort the list by n descending O(m.log(m))

4. now scan the list for solutions q<=m; O(q^2)

   so for each entry in list divide X'=X/list[j].p^list[j].n and now check X' the same way (using only entries with the same n). If you got X'=1 then stop the check and output your found result (power is used n and root is multiplication of all used primes). You need to check all the combinations of primes with same n so recursion is the way. If no combination of entries with the same n found with resulting in X'=1 then move to entries with different n with starting from X again.

The recursion could look like this:

    bool check(int X,int n,int j,int &a)
     {
     int i,x;
     for (;(list[j].n==n)&&(j<list.size);j++) // scan all primes with the same `n`
      {
      for (x=X,i=0;i<n;i++) x/=list[j].p;     // x=X/p^n
      if (x==1) { a*=list[j].p; return true; }// stop you hit the result
      if (check(x,n,j+1,a)) return true;      // recursion
      }
     return false;
     }

Where X is the number to check, n is actually checked power, j is starting entry in found list (no need to test previous entries as they have been already checked) and a is the base for power.If solution found returns true else false.

So now you just check all found powers with it and output/stop first found solution:

    int a,n,j; 
    for (j=0,n=list[j].n;j<list.size;)
     {
     a=1; if (check(X,n,j,a)) return solution X=a^n;// check power `n`
     while ((n==list[i].n)&&(j<list.size)) i++;     // find next power
     }
    return no solution found;

You can combine some of these steps together especially #1,#2 (even avoid recursion). If you need floating or fixed point approach or want to add some additional ideas for integers see and the sub-link too:

• How to calculate Python float-number-th root of float number

Here very similar Q/A with C++ solution covering your questio:

• Finding whether a number has P^Q form or not?