Solving $x^y + y^x = a$

Question

If $a$ is given how can I calculate $x^y$ and $y^x$ the fastest way? Is there any other way than brute forcing? How is this type of equation called?

Let's say $x$ and $y$ must be $>1$ and non negative integers.

Answer 1

Let's analyze this a bit, assuming that $x \le y$:

• For $x = 2$, you need to test $y = 2, 3, \dots, \lfloor \log_2 a \rfloor$.

• For $x = 3$, you need to test $y = 3, 4, \dots, \lfloor \log_3 a \rfloor$.

  ...

• The last $x$ is the biggest one for which $x^x \le a$. For example, for $a = 2^{64}$ (the first nonnegative integer number that fits in 64 bits), that's $x = 16$.

So, let $a = 2^{64}-1$. Then, we have $246$ candidates for a solution:

\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*}

I draw two conclusions from here:

1. Bruteforcing is simple.

2. Only a negligible number of these systems ($246$ among the first $2^{64}-1$) have solutions.

It's easier to go through all possible $(x,y)$, construct all $246$ values of $(x,y,a)$, put them in a file or a database, and just search for a solution when one is needed (and, most likely, doesn't exist).

The larger your numbers are, the less likely it is that you'll have a solution for any given $a$, so there is no point in going beyond $64$ bit (actually, there is no point going even that far).