I couldn't find anything on the Internet which could direct me to the solution of the following problem.

I want to know if $n$ can be calculated by $x^y$ where $y\ge 2$ and $x\ge 2$. I tried using $n$ modulus $x$, but this didn't worked out.

I'll use this formula in a computer application, the application must be able to apply this formula on numbers greater than $10^{14}$.

So the question is: Is there a formula to check if $n$ can be calculated by $x^y$?

Any hints, links and answers are appreciated. If you need more information, please feel free to ask.


In my application I have a given number n, this can be really anything. Anything here means larger than 1 and smaller than a number with one million digits, which is a pretty big range.
Now I need to know if n can be calculated with any power (NOT a product).

if n = 27. The formula should return true with: x = 3, y = 3.
if n = 12. The formula should return false. since it can only be calculated with products.
if n = 64. The formula should return true with: x = 2, y = 6.
NOTE: I need the smallest x. In the third example x could have been 8 with y = 2. But since I want the smallest x, I want x to be 2.

I need to know whether it is true or false. If the formula returns true, I also need to know x.

In all cases n, x and y should be positive whole numbers!

Update 2 Although I accepted an answer, new answers to improve the method are still welcome!

  • $\begingroup$ Isn't this, in a nutshell, the discrete logarithm problem? $\endgroup$
    – Asaf Karagila
    Commented Sep 16, 2011 at 8:59
  • $\begingroup$ @Asaf Karagila: I'm not a trained mathematician, please explain what you mean with 'discrete logarithm'. $\endgroup$
    – Mixxiphoid
    Commented Sep 16, 2011 at 9:06
  • 1
    $\begingroup$ And I am not a trained cryptographer. Try Google and Wikipedia, there should be a reasonable explanation there. $\endgroup$
    – Asaf Karagila
    Commented Sep 16, 2011 at 9:11
  • 1
    $\begingroup$ Why would you use a modulus here? Assuming that you want to check whether $n=x^y$ with $n,x,y$ all positive integers (otherwise it doesn't make much sense - barring the discrete log case): $x\ge 3$, so $y\le \log_3 n$. More often than not that logarithm is not too large a number, and you can test each possible value of $y$. May not be fast enough, but it's a start... $\endgroup$ Commented Sep 16, 2011 at 9:14
  • 2
    $\begingroup$ @Asaf: I'm not at all sure that this is about discrete logarithm. Mixxiphoid, please give a small toy example, so that we see what you want to do. Some points are still open to interpretation. $\endgroup$ Commented Sep 16, 2011 at 9:16

2 Answers 2


If you're trying to test if an integer is a (proper) power, it suffices to check if it's a p-th power for some prime up to its base-2 logarithm. This is pretty fast even for numbers in the range you ask for, where you'd only need about 14 tests. If you need a fast method for very large numbers, Bernstein, Lenstra & Pila's Detecting perfect powers by factoring into coprimes has an essentially-linear solution.

If you're asking about the same test mod a fixed value, then this is the discrete logarithm problem which is notoriously difficult. The best known methods for large values are the index calculus method and the number field sieve. Both are difficult to program.

If you need the greatest power, not just some power, you'll need to do slightly more work. One method: test all exponents, not just primes, up to the base-2 logarithm, in decreasing order. Faster method: test only the primes, but when you find that it is a power take the root and multiply an exponent variable (starting at 1) by the prime. So if you find that it's not a square but it is a third power, take the cube root and set the exponent to 3. Now test if what remains is a cube; if so, change the exponent to 9 and take the cube root again. If what remains is not a cube, continue testing for 5th, 7th 11th, etc. powers up to the new base-2 logarithm.

  • $\begingroup$ I will check this out, give me some time to apply it. $\endgroup$
    – Mixxiphoid
    Commented Sep 16, 2011 at 9:27
  • 1
    $\begingroup$ @Mixxiphoid: My recommendation is to implement a simple method first (check if it's a square, a cube, ... by taking roots) first, and only move to a more advanced algorithm like the one in the paper if it's unacceptably slow. Also note that checking for small prime factors (up to, say, 50) is worthwhile in most cases since that can significantly narrow the number of tests needed. If you find a prime p such that p^e divides n but p^(e+1) does not, then n can only be a power dividing e. $\endgroup$
    – Charles
    Commented Sep 16, 2011 at 9:32
  • $\begingroup$ You say 'check if it's a p-th power for some prime up to its base-2 logarithm.' Do you mean that I should do $p^2$$^l$$^o$$^g$$^($$^n$$^)$? Where p is a prime up to ~50? I need y in $x^y$ to be a whole number. $\endgroup$
    – Mixxiphoid
    Commented Sep 16, 2011 at 10:31
  • 3
    $\begingroup$ @Mix, no. Just for each prime $p$ with $p\le\log_2(n)$ you take the $p$th root of $n$ and check whether it's an integer. In fact, since you want $x\ge 3$ you only have to check at $p\le\log_3(n)$. $\endgroup$ Commented Sep 16, 2011 at 11:52
  • $\begingroup$ @Henning Makholm: Thanks for your clarification, I will implement this. $\endgroup$
    – Mixxiphoid
    Commented Sep 16, 2011 at 12:51

As Charles said, you only need to check, for all primes $p < \log_2 n$, whether $n$ is a $p$-th power. To get you started, here is a simple method for finding the integral part of the $p$-th root of $n$:

  1. Find the largest power of two that is $\le n^{1/p}$ (this is just $2^{\lfloor(\log_2 n)/p\rfloor}$)
  2. Fill in the binary digits one by one, from most significant to least signicifant: at each step, try a $1$ in the next most significant place, and raise it to the $p$-th power; if the result is greater than $n$, replace the $1$ with a $0$.

This is by no means the fastest method, but it should be fast enough to get results.

  • $\begingroup$ Thanks for your answers, I will try to implement it and see how it works. $\endgroup$
    – Mixxiphoid
    Commented Sep 16, 2011 at 12:48
  • $\begingroup$ You get my support. It's always good to have an explicit algorithm when someone is looking to implement the problem at hand. I think it runs at roughly n log n operations (for an n-bit input) compared to roughly n operations for Bernstein's method, so it's not particularly slow either. $\endgroup$
    – Charles
    Commented Sep 17, 2011 at 18:40
  • $\begingroup$ Would divide and conquer do? Find $x$ and $y$ such that $n = xy$. If $x = y$, then RETURN(TRUE, $x,2$). Otherwise, see if $x$ and $y$ are powers. etc. $\endgroup$ Commented Jul 25, 2015 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .