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$?
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!
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.
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$:
- Find the largest power of two that is $\le n^{1/p}$ (this is just $2^{\lfloor(\log_2 n)/p\rfloor}$)
- 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.