## Puzzle : Power game

Well,

I like the dramatic titles :-). Anyways, here goes the problem.

Problem : Given an integer n, determine whether $n=a^b$ for some integers a and b in poly-logarithmic time.

Solution : It is obvious that for certain n, there could be multiple a’s and b’s such that $n=a^b$. We only need to find one such a and b or have to declare that there are no such integers. Needless to say, that we are ruling out b=1 :-).

Given any n, the number of bits required is log n. Now, let us fix b = 2. For this b,  a must be having $\lceil \frac{log n}{2} \rceil$ bits. So we know the range of possible a’s that might satisfy $a^2=n$. We do a binary search on this range in O(log n) time. If we do not find a suitable a, we fix b=3 and repeat. There can be only logarithmic many such b’s. Multiplication and calculating powers of a number, both can be done in polylog time. Hence, we can determine that the given number n is of the form $a^b$ for some n or not.

Cool, isn’t it?

–Saurabh Joshi