Author |
Topic: number of form m^n (Read 1880 times) |
|
inexorable
Full Member
Posts: 211
|
 |
number of form m^n
« on: May 18th, 2011, 7:38pm » |
 Quote  Modify
|
give an algorithm to find if a given integer is of the form m^n where m >1 and n >1
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: number of form m^n
« Reply #1 on: May 18th, 2011, 10:39pm » |
Quote Modify
|
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;
}
|
| « Last Edit: May 18th, 2011, 10:44pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: number of form m^n
« Reply #2 on: Jul 6th, 2011, 11:19am » |
Quote Modify
|
@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..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: number of form m^n
« Reply #3 on: Jul 6th, 2011, 11:44am » |
Quote Modify
|
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 = mn <=> ln(x) = n*ln(m)
However, if you can use floating point arithmetic thing will get much trickier.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: number of form m^n
« Reply #4 on: Dec 25th, 2011, 9:06pm » |
Quote Modify
|
I think doing a binary search for N would do here. That would take O(LogN) time.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: number of form m^n
« Reply #5 on: Dec 26th, 2011, 12:11am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print