# How to know if a number is a power of $x$

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$?

Greetings,
Mixxiphoid

Update:
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).

Example:
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!

-
Isn't this, in a nutshell, the discrete logarithm problem? –  Asaf Karagila Sep 16 '11 at 8:59
@Asaf Karagila: I'm not a trained mathematician, please explain what you mean with 'discrete logarithm'. –  Mixxiphoid Sep 16 '11 at 9:06
And I am not a trained cryptographer. Try Google and Wikipedia, there should be a reasonable explanation there. –  Asaf Karagila Sep 16 '11 at 9:11
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... –  Jyrki Lahtonen Sep 16 '11 at 9:14
@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. –  Jyrki Lahtonen Sep 16 '11 at 9:16

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.

-
I will check this out, give me some time to apply it. –  Mixxiphoid Sep 16 '11 at 9:27
@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. –  Charles Sep 16 '11 at 9:32
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. –  Mixxiphoid Sep 16 '11 at 10:31
@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)$. –  Henning Makholm Sep 16 '11 at 11:52
@Henning Makholm: Thanks for your clarification, I will implement this. –  Mixxiphoid Sep 16 '11 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.

-
Thanks for your answers, I will try to implement it and see how it works. –  Mixxiphoid Sep 16 '11 at 12:48
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. –  Charles Sep 17 '11 at 18:40