Elegant way to solve $n\log_2(n) \le 10^6$ I'm studying Tomas Cormen Algorithms book and solve tasks listed after each chapter.
I'm curious about task 1-1. that is right after Chapter #1.
The question is: what is the best way to solve: $n\lg(n) \le 10^6$, $n \in \mathbb Z$, $\lg(n) = \log_2(n)$; ?
The simplest but longest one is substitution. Are there some elegant ways to solve this? Thank you!
Some explanations: $n$ - is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out nmax.
 A: The first approximation for the inverse of $x\;\text{lg}\; x$ is $x/\text{lg}\; x$.  So begin with the value $10^6/\text{lg}(10^6)$, then adjust by substitution/bisecion.
A: First, I found a power of 2, $n=2^p$, such that $n\log_2 n=2^p\cdot p\approx 10^6$. Since $2^{20}\approx 10^6$, it's probably going to be a click or two below that. Sure enough, $16\cdot 2^{16}=2^{20}=1048576$.
Now I figured that $\log_2 n \approx 16$, so $n \approx 10^6/16=62500$. Sure enough, for that $n$, $n\log_2 n \approx 995723$. 
Now some simple searching or bisection will do the trick: $63000$ and $62750$ are too large; $62625$, $62700$, $62725$ are too small; etc. The number of bisection steps, if you use strict halving of the interval, is bounded by $\log_2 n$. So you know you'll get there quickly. Eventually I found that if $n=62746$, $n\cdot\log_2 n \approx 999998$.
That is the largest possible integer $n$; so $n\leq 62746$ is your answer.
EDIT: earlier I suggested that Newton's method was too beefy for the job. Well, I think I'm wrong. After all, the derivative of $f(n)=n\log_2 n$ is just $f'(n)=\log_2 n+\log_2 e$, and you have to compute $\log_2(n)$ anyway every time you do a bisection step. So the derivative information is there, free to use. If I were coding up an algorithm, yes I think I would do Newton's method. A similar case could be made for using Newton's even for the initial $p\cdot 2^p$ search.
A: For my money, the best way is to solve $n\log_2n=10^6$ by Newton's Method. 
A: If something cheesier than Newton's method is wanted, I recommend the fixed point iteration:
x := (10^6)/log_2(x) 

This is easily done with a calculator applet by storing constant (10^6) * log_10(2) and thereafter taking $\log_{10}(x)$, reciprocating, and then multiplying by the recalled constant.
Starting with obvious overestimate $x_0 = 10^6$, the fixed-point iterates alternate between under- and over-shooting:
x1 = 50,171.67
x2 = 64,042.69
x3 = 62,630.17
x4 = 62,756.63
x5 = 62,745.18
x6 = 62,746.21
x7 = 62,746.12

Thus the largest possible integer is $n = 62746$, as Michael already stated.
A: To solve for $n\log_2(n)=10^6$, we can use the Lambert-W function. A bit of manipulation yields
$$
\log(n)e^{\log(n)}=10^6\log(2)
$$
and the Lambert-W function, being the inverse of $xe^x$, says that
$$
\log(n)=\mathrm{W}\left(10^6\log(2)\right)
$$
or
$$
n=\exp\left(\mathrm{W}\left(10^6\log(2)\right)\right)
$$
on the positive reals, the Lambert-W function is monotonically increasing, so you can simply get the desired inequality.
Mathematica gives the result $62746.1264697$ for N[Exp[LambertW[10^6Log[2]]],12].
Therefore, the largest $n$ is $62746$.
A: I think Newton's Method and Fixed-Point Iteration are too complicated when you're looking for an integer. A simple Binary Search would be much more effective,
and probably faster if you don't need as many floating-point operations.
I give more details on my answer on this question's duplicate on CS.SE.
