I'm preparing for my interviews and came across this question:
Write a program to check if a number n is of x^y form. It is known that n, x and y are integers and that x and y are greater than 2.
I thought of taking log and stuff but couldn't certainly figure out how to check if the number is of the form. Could any of you please help? :)
"Taking the log and stuff" is the way to go. Note that N > 1 is never a^b for integer a and b > log_2(N). So you can check floor(N^(1/b))^b = N for each integer b between 2 and log_2(N). You have to do about log(N) many exponentiations, each of which produces a number at most the size of N.
This is far faster than @dasblinkenlight's solution, which requires you to factor N first. (No polynomial-time algorithm---that is, polynomial in the number of bits in N, is known for integer factorisation. However, integer exponentiation with a small exponent can be done in polynomial time.)
One way to solve this would be to factorize n, count the individual factors, and find the greatest common denominator of the counts. If GCD is 1, the answer is "no". Otherwise, the answer is "yes".
Here are some examples:
If you can factor n, then it is easy to find an answer by examining the multiplicities of the factors. But the usual use for determining if a number is a perfect power is as a preliminary test for some factoring algorithms, in which case it is not realistic to find the factors of n.
The trick to determining if a number is a perfect power is to know that, if the number is a perfect power, then the exponent e must be less than log2 n, because if e is greater then 2e will be greater than n. Further, it is only necessary to test prime es, because if a number is a perfect power to a composite exponent it will also be a perfect power to the prime factors of the composite component; for instance, 215 = 32768 = 323 = 85 is a perfect cube root and also a perfect fifth root. Here is pseudocode for a function that returns b if there is some exponent e such that be = n or 0 if there is not; the function root(e,n) returns the e-th root of n:
function perfectPower(n)
for p in primes(log2(n))
b = floor(root(p,n))
if b**p == n return b
return 0
I discuss this function at my blog.
There are a lot of good answers, but I see modulo arithmetics is still missing.
Depending on the magnitude of the numbers to check, it might be useful to classify them by their last bits. We can easily create a table with possible candidates.
To show how it works, let us create such a table for 4 last bits. In that case we have 16 cases to consider:
0^2, 0^3, ... : 0 mod 16
1^2, 1^3, ... : 1 mod 16
2^2, 2^3, ... : 0, 4, 8 mod 16
3^2, 3^3, ... : 9, 11, 1, 3 mod 16
4^2, 4^3, ... : 0 mod 16
5^2, 5^3, ... : 9, 13, 1, 5 mod 16
6^2, 6^3, ... : 4, 8, 0 mod 16
7^2, 7^3, ... : 1, 7 mod 16
8^2, 8^3, ... : 0 mod 16
9^2, 9^3, ... : 9, 1 mod 16
10^2,10^3, ... : 4, 8, 0 mod 16
11^2,11^3, ... : 9, 3, 1, 11 mod 16
12^2,12^3, ... : 0 mod 16
13^2,13^3, ... : 9, 5, 1, 13 mod 16
14^2,14^3, ... : 4, 8, 0 mod 16
15^2,15^3, ... : 1, 15 mod 16
The table is more useful the other way round; which bases x are possible for a given number n = x^y.
0: 0, 2, 4, 6, 8, 10, 12, 14 mod 16
1: 1, 3, 5, 7, 9, 11, 13, 15
2: -
3: 3, 11
4: 2, 6, 10, 14
5: 5, 13
6: -
7: 7
8: 2, 6, 10, 14
9: 3, 5, 9, 11, 13
10: -
11: 3, 11
12: -
13: 5, 13
14: -
15: 15
So, just by looking at the four last bits over one quarter of numbers can be discarded immediately.
If we take number 13726423, its remainder by 16 is 7, and thus if it is of the form we are interested in, it must be (16 n+7)^y.
For most numbers the number of divisors to try is quite limited. In practice, the table could me much larger, e.g., 16 bits.
A simple optimization with binary numbers is to remove the trailing zeros. This makes it unnecessary to worry about even numbers, and y must be a factor of the number of the zeros removed.
If we still have too much work, we can create another modulo table. The other could be, e.g. modulo 15. The equivalent table looks like this:
0: 0
1: 1, 2, 4, 7, 8, 11, 13, 14
2: 2, 8
3: 3, 12
4: 2, 4, 7, 8, 13
5: 5
6: 3, 6, 9, 12
7: 7, 13
8: 2, 8
9: 3, 9, 12
10: 5, 10
11: 11
12: 3, 12
13: 7, 13
14: 14
As our number from the previous example (13726423) is 13 modulo 15, then x = (15 m +7) or (15 m +13). As there are no common factors in 15 and 16, the valid numbers are 240 p + 7 and 240 p + 103. By two integer divisions and two table lookups we have managed to limit the possible values of x to 1/120 of numbers.
If the tables are largish, the number of possible x s is easy to limit to a very low number. For example, with tables of 65536 and 65535 elements the cycle is 4294901760, so for any number below approximately 1.6 x 10^19 the two tables give a short unique list of possible values of x.
Alternatively, if factorization is too hard, you can exploit your maths library and try many values of x or y until you find one that works.
Trying for y will be less work, if you have an operation "y-th root of n" available (it could be masquerading under the name of "x to the power of 1/y"). Just try all integer values of y larger than 2 until either you find one that gives an integer answer, or the result drops below 2. If n is a standard 32-bit integer, then it will take no more than 32 attempts (and, more generally, if n is a m-bit integer, then it will take no more than m attempts).
If you do not have "y-th root of n" available, you can try all x's with the operation "log base x of n", until you get an integer answer or the result drops below 2. This will take more work since you need to check all values up until square root of x. I think it should be possible to optimize this somehow and "home in" on potential integer results.
The exponent y is easily bounded 2 ≤ y ≤ log_2(n) . Test each y in that range. If it exists, x will be the integer yth root of n.
The point is while x determines y and vice versa, the search space for y is much smaller, so you should search y rather than x (which could be as large as sqrt(n)).
