Well,

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

**Problem : ** Given an integer n, determine whether 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 . 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 bits. So we know the range of possible a’s that might satisfy . 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 for some n or not.

Cool, isn’t it?

–Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: algorithm, math, puzzle

This entry was posted on October 13, 2010 at 5:38 am and is filed under algorithm, math, puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply