If a number is of type $n^n$, how to identify that? Example: 256 is $4^4$, 3125 is $5^5$

If a number is of type $n^n$, how to identify that? Example: 256 is $4^4$, 3125 is $5^5$. I have to write a code for that.

Solution 1:

How big can your input be (let's call it $r$)? If it is a 64-bit integer, then you only have to try $n=1,\ldots,15$, because $16^{16} = 2^{64}$ is already too big. The easiest way is to pre-calculate these 15 values, so you can just look them up in a table.

If $r$ is an arbitrary-length integer, then you still only have to try $n$ up to $\log_2r$, i.e. the bit-length of $r$. In fact you can check if all prime factors of $r$ are $\le \log_2r$ (you don't need to find all the prime factors to do this, just those that are $\le \log_2r$); if not, then $r$ is not of the form $n^n$. If all prime factors are this small, you can easily factorise $r$, and then you can check each possible $n$ very efficiently.

Solution 2:

The inverse of $y=x^x$ is $x=e^{W(\ln(y))}$. If this is an integer, then $y$ is of the given type. W(x) is the Lambert W function here.