It's one of the questions from the practice section in hackerearth. We need to determine whether m^n = n^m. It is trivial when n = m, so we focus on m != n.
1 <= m, n <= 10^10000
What I have tried is
n^m = m^n implies
m*log(n) = n*log(m)
But the problem is how to take log of such a huge number? Is there an alternative way of checking equality?
Let's do some math to determine how to program for solutions:
It is easy to see that neither n nor m can equal 1 as they must be different and cannot be null. Let's look for solutions where 1 < n < m.
As you correctly stated, nm = mn implies m.log(n) = n.log(m)
hence we are looking for solutions to m / log(m) = n / log(n) and 1 < n < m.
We can study the function f(x) = x / log(x) for x > 1:
Its derivative is f'(x) = (log(x) - 1) / log(x)2
The derivative has a single zero at x = e, f(x) is strictly decreasing between x = 1 and x = e and strictly increasing from x = e all the way to infinity.
Any 2 distinct numbers n and m such that f(n) = f(m), n < m must be such that 1 < n < e and m > e
The only possible integer value for n is 2 and it happens to be a solution with the corresponding value of m as 4, there is no other integer in the interval 1 to e.
Hence the only solutions are n=2, m=4 and n=4, m=2
Here is a C program to output all possible results:
#include <stdio.h>
int main() {
printf("2 4\n");
printf("4 2\n");
return 0;
}