Detecting if n is of the form a^b
Posted 03 November 2004 - 11:03 PM
It asks to determine, for a given natural number n, if n = a^b for some natural numbers a and b > 1. I've thought of taking the logarithm of n; this gives log n = b log a, but doesn't seem to help the determination if a and b are natural numbers (obviously, if one allows a and b to be real numbers, there are infinitely many solutions to n = a^.
This isn't an essential part of the algorithm as it's basically an early-out, but I'm curious anyways.
How do you tell whether n is of the form a^b?
Posted 04 November 2004 - 07:13 AM
And, honestly I don't know of a better idea, because you want to find the values of two constants, but you only have one equation. :sad:
Edited for length.
Posted 04 November 2004 - 07:36 AM
Brute force would work, though I was hoping for something better =D
Posted 04 November 2004 - 07:45 AM
Posted 04 November 2004 - 07:50 AM
Although looking closer at the problem, I think it is safe to say that if n=a^b then this means that n can be divided by a exactly b times, so it would make sense to furhter investigate only those values of a that divide n. This doesn't give an exact solution but further narrows the interval for valid values of a and b. For instance if n is 9, there is no need to check for values of a like 2, 4, 5,...
What do you mean by multiple solutions in this context ?
Posted 04 November 2004 - 01:20 PM
Scroll to the Other arithmetic operations section
Some really nice and seemingly interesting papers here
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users