wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> number of form m^n
        
(Message started by: inexorable on May 18^th, 2011, 7:38pm)

Title: number of form m^n
Post by inexorable on May 18^th, 2011, 7:38pm

give an algorithm to find if a given integer is of the form m^n where m >1 and n >1

Title: Re: number of form m^n
Post by towr on May 18^th, 2011, 10:39pm

[hide]x = ln(m**n)
for (i = 2; i <= x/ln(2); i++)
{
y = round(exp(x/i));
if(y**i == m**n)
print y,i;
}[/hide]

Title: Re: number of form m^n
Post by singhar on Jul 6^th, 2011, 11:19am

@tower, Could you explain what is this algo doing:

I was thinking of finding the prime factors below sqrt(N) and then finding how many times each one of them repeats..

Title: Re: number of form m^n
Post by towr on Jul 6^th, 2011, 11:44am

I'm searching for possible exponents in that algorithm. The largest exponent would be when m=2, and is ln(x)/ln(2). So I can just search for the few possible exponent between 2 and ln(x)/ln(2).
Basically I exploit the identity: x = mⁿ <=> ln(x) = n*ln(m)

However, if you can use floating point arithmetic thing will get much trickier.

Title: Re: number of form m^n
Post by Dufus on Dec 25^th, 2011, 9:06pm

I think doing a binary search for N would do here. That would take O(LogN) time.

Title: Re: number of form m^n
Post by towr on Dec 26^th, 2011, 12:11am

I don't see how that could possibly work. Bear in mind that you don't know m. There's nothing to tell you whether some candidate you tried is greater or smaller than the real n you're after.