Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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!

share|improve this question
    
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
1  
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
1  
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
2  
@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
show 7 more comments

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer
    
I will check this out, give me some time to apply it. –  Mixxiphoid Sep 16 '11 at 9:27
1  
@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
3  
@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
show 2 more comments

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.