How to solve $n\times\log_2(n)=10^6$

Question

Sorry for my bad English.

I started to read book about algorithms(Introduction to Algorithms) and there is a problem, I should find a valid $n$ for $$n \times \log_2(n) = q $$ q might be very big number ($3\times10^{15}$)

I know that I can write a regular brute force program, but it doesn't work, if q is very large number.

The exact solution uses Lambert W, so... go for numerics, known or home-grown. — metamorphy, Aug 05 '22 at 09:31
Use a change of basis $\log_2n=\frac{\ln n}{\ln2}$ then solve for $n$ and then as stated by @metamorphy, use the Lambert function. — joseph h, Aug 05 '22 at 09:33
In the Wikipedia page, there is a series approximation in terms of the logarithms. — Claude Leibovici, Aug 05 '22 at 11:09

score 0 · Accepted Answer · answered Aug 05 '22 at 09:40

With $\log_2(n) = \frac{\ln(n)}{\ln(2)}$ your equation becomes \begin{align} n \frac{\ln(n)}{\ln(2)} &= q \\ \Leftrightarrow n \ln(n)&= q\ln(2) \\ \Leftrightarrow n \ln(n)&= \widetilde{q}. \end{align} Then, perform the change of variables $\widetilde{n} := \ln(n)$. This implies that $e^\widetilde{n} = e^{\ln(n)} = n$. Thus, your equation becomes

\begin{align} \widetilde{n} e^{\widetilde{n}} = \widetilde{q}. \end{align} Using the Lambert W function, this can be then be (numerically) solved for $\widetilde n = W(\widetilde q)$ and then $n$.

How to solve $n\times\log_2(n)=10^6$

1 Answers1