¿Cómo saber si un número es una potencia de $x$?

Question

No pude encontrar nada en Internet que me pudiera llevar a la solución del siguiente problema.

Quiero saber si $n$ puede ser calculado por $x^y$ donde $y\ge 2$ y $x\ge 2$. Intenté usando $n$ módulo $x$, pero esto no funcionó.

Utilizaré esta fórmula en una aplicación de computadora, la aplicación debe ser capaz de aplicar esta fórmula en números mayores a $10^{14}$.

Entonces la pregunta es: ¿Hay una fórmula para verificar si $n$ puede ser calculado por $x^y$?

Se agradecen cualquier pista, enlace y respuesta. Si necesitas más información, no dudes en preguntar.

Saludos,
Mixxiphoid

Actualización:
En mi aplicación tengo un número dado n, esto realmente puede ser cualquier cosa. Cualquier cosa aquí significa mayor a 1 y menor que un número con un millón de dígitos, que es un rango bastante grande.
Ahora necesito saber si n puede ser calculado con cualquier potencia (NO un producto).

Ejemplo:
si n = 27. La fórmula debería devolver verdadero con: x = 3, y = 3.
si n = 12. La fórmula debería devolver falso. ya que solo puede ser calculado con productos.
si n = 64. La fórmula debería devolver verdadero con: x = 2, y = 6.
NOTA: Necesito el x más pequeño. En el tercer ejemplo x podría haber sido 8 con y = 2. Pero como quiero el x más pequeño, quiero que x sea 2.

Necesito saber si es verdadero o falso. Si la fórmula devuelve verdadero, también necesito saber x.

En todos los casos n, x y y deben ser números enteros positivos!

Actualización 2 Aunque acepté una respuesta, ¡nuevas respuestas para mejorar el método todavía son bienvenidas!

Answer 1

Si estás tratando de probar si un entero es una potencia (correcta), basta con verificar si es una potencia de p para algún primo hasta su logaritmo en base 2. Esto es bastante rápido incluso para números en el rango que estás preguntando, donde solo necesitarías alrededor de 14 pruebas. Si necesitas un método rápido para números muy grandes, el documento de Bernstein, Lenstra & Pila Detectar potencias perfectas factorizando en coprimos tiene una solución esencialmente lineal.

Si estás preguntando sobre la misma prueba módulo un valor fijo, entonces esto es el problema del logaritmo discreto que es notoriamente difícil. Los mejores métodos conocidos para valores grandes son el método del cálculo de índices y la criba de cuerpos de números. Ambos son difíciles de programar.

Si necesitas la mayor potencia, no solo alguna potencia, necesitarás hacer un poco más de trabajo. Un método: probar todos los exponentes, no solo los primos, hasta el logaritmo en base 2, en orden decreciente. Método más rápido: probar solo los primos, pero cuando descubras que es una potencia, toma la raíz y multiplica una variable de exponente (comenzando en 1) por el primo. Así que si descubres que no es un cuadrado pero es una potencia de tercero, toma la raíz cúbica y establece el exponente en 3. Ahora prueba si lo que queda es un cubo; si es así, cambia el exponente a 9 y toma la raíz cúbica nuevamente. Si lo que queda no es un cubo, continúa probando para potencias de 5, 7, 11, etc. hasta el nuevo logaritmo en base 2.

Answer 2

Como dijo Charles, solo necesitas verificar, para todos los primos $p < \log_2 n$, si $n$ es una potencia $p$-ésima. Para comenzar, aquí tienes un método simple para encontrar la parte entera de la raíz $p$-ésima de $n:

1. Encuentra la mayor potencia de dos que sea $\le n^{1/p}$ (esto es simplemente $2^{\lfloor(\log_2 n)/p\rfloor}$)
2. Rellena los dígitos binarios uno por uno, de más significativo a menos significativo: en cada paso, prueba un $1$ en el siguiente lugar más significativo, y elevalo a la $p$-ésima potencia; si el resultado es mayor que $n$, reemplaza el $1$ con un $0$.

Este método no es precisamente el más rápido, pero debería ser lo suficientemente rápido para obtener resultados.