Solving $y^y = x$ for large $x$

Question

I was playing around with recurrence relations and noticed that $\sqrt x$ has the fun property that $$\frac{x}{f(x)} = f(x)$$ ($\sqrt{x}$ and its negation are the only functions $f(x)$ that satisfy this it).

That got me thinking about what functions satisfy $$\sqrt[f(x)]{x} = f(x).$$

These functions need to satisfy $$x = f(x)^{f(x)}.$$

If we let $y = f(x)$, this boils down to solving $$y^y = x.$$

I am having trouble seeing how to solve this. My initial thought was to take the log of both sides, giving

$$y \log y = \log x,$$

and then tried seeing if the change-of-basis formula would help, since the above statement implies that

$$y = \log_y x,$$

but this didn't seem to offer any clarity.

Is there a nice way to solve this equation? Or is there a known name for a function of $x$ that's specifically designed to have this property?

Answer 1

The Lambert W function $W$ is defined to be the inverse of the map $z \mapsto z e^z$ (or more precisely, its restriction to $[0, \infty)$). A little algebra shows that a solution $x$ to $x^x = y$ is (for suitable $y$) $$x = e^{W(\log y)} = \frac{\log y}{W(\log y)} .$$

Answer 2

No, there is no nice way. (Think about it this way: how would you solve $x*x=y$, if you didn't know about the square root function? The square root was invented to solve $x*x=y$; you need another special function to solve $x^x = y$ (and as Travis mentions above, a very similar such function is called the Lambert $W$-function.)

What if you want to find an approximate solution? This is a great place to try Newton's method. If you want to solve $f(x)=y$, and you have some initial guess $x_0$, Newton's method lets you find a better guess (usually) using the formula $$x_1 = x_0 - [f(x_0)-y]/f'(x_0)$$ where $f'$ is the derivative. For the case $f(x) = x \log x$ and $\log y$ we have $$x_1 = x_0 - (x_0\log x_0 - \log y)/(\log x_0 + 1)$$ (if you haven't taken Calculus yet, you will have to take it for granted for now how I got that term in the denominator.)

And we can repeat this process to get better and better guesses: $$x_{i+1} = x_i - (x_i\log x_i - \log y)/(\log x_i + 1).$$

We can try this with $y=1000$. Since $x\log x \approx x$, we will pick $x_0 = \log y = 6.9$ as our initial guess. Plugging into the formula repeatedly I get $$\begin{array}{lc}x_0 & 6.9\\x_1 & 4.7101\\x_2 & 4.55654\\ x_3 & 4.55554 \\ x_4 & 4.55554\end{array}$$

The numbers have stopped changing, so the method has finished: I check $$4.55554^{4.55554} = 1000.01$$ so I have a pretty good estimate of the right value of $x$.

Interestingly, this same approach was used to calculate $\sqrt{x}$ by the ancient Babylonians, before calculators (and before Newton invented the general method).