Puzzle : Power game


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


Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: