How to find the inverse function of $f(n) = n \ log_2(n)$

Question

Is there a way to rearrange such a function to a form like $n = \text{something}$ ?

Answer 1

Here's a form that looks interesting. For $m=n\log_2n>4$, we have

$$n=\frac{m}{\log_2n}=\frac{m}{\log_2\frac{m}{\log_2n}}=\cdots =\frac{m}{\log_2\frac{m}{\log_2\frac{m}{\log_2\cdots}}}.$$

Looks like a continued fraction. But it's continued logarithm. Not sure if it's useful though.

Answer 2

If $m = n \log_2 n$

then $m\ln 2 = n\ln n$

Lambert W-function is the inverse of $g(a)=a \exp(a)$, that is

$$W(a \exp(a))=a$$ and hence by letting $a=\ln n$, $$W(n\ln n ) = \ln n$$

Hence from $m \ln 2 = n \ln n$, by taking the lambert W-function,

$$W(m \ln 2) = W(n \ln n)= \ln n$$

Hence $$n = \exp(W(m \ln 2))$$

Remark: If you are alright with a numerical algorithm, bisection should work.

Answer 3

$$y=n \log_2 n = \frac{ n \ln n }{\ln 2}$$

$$y \ln 2 = n \ln n$$

Now, let $n=e^m$

$$y \ln 2 = me^m$$

$$y \ln 2 = W(m)$$

Where $W(m)$ is Lambert W Function.

So, finally we've : $$y = \frac{W(\ln n)}{\ln 2}$$

Answer 4

If you're looking for an answer at the level of high school or introductory college algebra, then it suffices to look at the plot of the function.

Here, it is easy to see that the function will not be invertible, as it does not pass the "horizontal line test". More mathematically, this means that, as we need a function to send each number to one AND ONLY ONE other number, if we "flip" this function around the line $y = x$ to see what it's inverse will look like, we see that the point $-0.25$ will get sent to more than one number by the proposed "inverse", which will cause this inverse to not be a function.

If a more sophisticated or partial answer is desired, then the other solutions posted may be better suited towards your needs.

Answer 5

Taking into account your comments after answers, let me suppose that, for a given $m$, you want to find numerically the zero of equation $$f(n)= n \log_2 n-m=\frac{n \log (n)}{\log (2)}-m$$ Newton method will work very well, giving as iterates $$n_{k+1}=\frac{m \log (2)+n_k}{1+\log (n_k)}$$ Assuming that $m$ is large, you can use the expansion given in the Wikipedia page $$W(x)=L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\cdots$$ where $L_1=\log(x)$ and $L_2=\log(L_1)$. Using it, you can estimate $n_0$ from $$n=\frac{m \log (2)}{W(m \log (2))}$$

Just for illustration purposes, let us use the above for $m=10^p$. The following table gives the so-generated $n_0$ and the exact solution for six significant figures. $$\left( \begin{array}{ccc} p & n_0 & n \\ 1 & 4.62524 & 4.56496 \\ 2 & 22.2676 & 22.3201 \\ 3 & 140.099 & 140.222 \\ 4 & 1002.66 & 1003.00 \\ 5 & 7739.82 & 7740.96 \\ 6 & 62741.7 & 62746.1 \\ 7 & 526153. & 526172. \\ 8 & 4.52298\times 10^6 & 4.52307\times 10^6 \\ 9 & 3.96196\times 10^7 & 3.96201\times 10^7 \\ 10 & 3.52211\times 10^8 & 3.52213\times 10^8 \\ 11 & 3.16844\times 10^9 & 3.16845\times 10^9 \\ 12 & 2.87815\times 10^{10} & 2.87816\times 10^{10} \end{array} \right)$$ If you need to polish the solution, Newton method will converge in very few iterations to any level of accuracy. This is shown below for $m=10^{12}$ $$\left( \begin{array}{cc} k & n_k \\ 0 & \color{red}{2.87815}16538653414818921185148671484133102881821078\times 10^{10} \\ 1 & \color{red}{2.878159387735}9627781531535908737458118462461822980\times 10^{10} \\ 2 & \color{red}{2.87815938773554852079111735}81957990069957764041854\times 10^{10} \\ 3 & \color{red}{2.8781593877355485207911173570072526567345563696090}\times 10^{10} \end{array} \right)$$