La resolución de $x^y + y^x = a$

Question

Si $a$ es dado ¿cómo puedo calcular el $x^y$ $y^x$ la manera más rápida? ¿Hay algún otro modo de fuerza bruta? Cómo es que este tipo de ecuación se llama?

Vamos a decir $x$ $y$ debe $>1$ y no enteros negativos.

Answer 1

Vamos a analizar esto un poco, suponiendo que $x \le y$:

• Para $x = 2$, usted necesita para poner a prueba $y = 2, 3, \dots, \lfloor \log_2 a \rfloor$.

• Para $x = 3$, usted necesita para poner a prueba $y = 3, 4, \dots, \lfloor \log_3 a \rfloor$.

  ...

• La última $x$ es el mayor para que $x^x \le a$. Por ejemplo, para $a = 2^{64}$ (el primer número entero no negativo que encaja en la versión de 64 bits), que es $x = 16$.

Por lo tanto, vamos a $a = 2^{64}-1$. Entonces, tenemos $246$ candidatos para una solución:

\begin{align*} &x = 2 \quad \Rightarrow \quad y \in \{2,3,\dots,63\}, \\ &x = 3 \quad \Rightarrow \quad y \in \{3,4,\dots,40\}, \\ &x = 4 \quad \Rightarrow \quad y \in \{4,5,\dots,31\}, \\ &x = 5 \quad \Rightarrow \quad y \in \{5,6,\dots,27\}, \\ &x = 6 \quad \Rightarrow \quad y \in \{6,7,\dots,24\}, \\ &x = 7 \quad \Rightarrow \quad y \in \{7,8,\dots,22\}, \\ &x = 8 \quad \Rightarrow \quad y \in \{8,9,\dots,21\}, \\ &x = 9 \quad \Rightarrow \quad y \in \{9,10,\dots,20\}, \\ &x = 10 \quad \Rightarrow \quad y \in \{10,11,\dots,19\}, \\ &x = 11 \quad \Rightarrow \quad y \in \{11,12,\dots,18\}, \\ &x = 12 \quad \Rightarrow \quad y \in \{12,13,\dots,17\}, \\ &x = 13 \quad \Rightarrow \quad y \in \{13,14,\dots,17\}, \\ &x = 14 \quad \Rightarrow \quad y \in \{14,15,16\}, \\ &x = 15 \quad \Rightarrow \quad y \in \{16\}, \end{align*}

Extraigo dos conclusiones a partir de aquí:

1. Bruteforcing es simple.

2. Sólo un número insignificante de estos sistemas ($246$ entre el primer $2^{64}-1$) tienen soluciones.

Es más fácil ir a través de todos los posibles $(x,y)$, construir todas las $246$ valores de $(x,y,a)$, ponerlos en un archivo o en una base de datos, y sólo la búsqueda de una solución cuando es necesario (y, probablemente, no existe).

Los más grandes son tus números, menos probable es que usted va a tener una solución para cualquier $a$, así que no hay ningún punto en ir más allá de $64$ poco (en realidad, no hay ningún punto de ir más lejos).