Si un número es del tipo $n^n$ ¿Cómo identificarlo? Ejemplo: 256 es $4^4$ , 3125 es $5^5$

Question

Si un número es del tipo $n^n$ ¿Cómo identificarlo? Ejemplo: 256 es $4^4$ , 3125 es $5^5$ . Tengo que escribir un código para eso.

Answer 1

¿Qué tamaño puede tener su entrada (llamémosla $r$ )? Si se trata de un entero de 64 bits, entonces sólo tiene que intentar $n=1,\ldots,15$ porque $16^{16} = 2^{64}$ ya es demasiado grande. La forma más sencilla es calcular previamente estos 15 valores, de modo que puedas consultarlos en una tabla.

Si $r$ es un entero de longitud arbitraria, entonces sólo tiene que probar $n$ hasta $\log_2r$ es decir, la longitud en bits de $r$ . De hecho se puede comprobar si todos los factores primos de $r$ son $\le \log_2r$ (no es necesario encontrar todos los factores primos para hacer esto, sólo los que son $\le \log_2r$ ); si no, entonces $r$ no es de la forma $n^n$ . Si todos los factores primos son así de pequeños, se puede factorizar fácilmente $r$ y, a continuación, puede comprobar cada posible $n$ muy eficazmente.

Answer 2

La inversa de $y=x^x$ es $x=e^{W(\ln(y))}$ . Si es un número entero, entonces $y$ es del tipo indicado. W(x) es aquí la función W de Lambert.