Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$

I'm studying CLRS, and solving problems listed after each chapter. I'm curious about problem 1-1. That is right after Chapter 1.

The question is, what is the best way to find the largest integer $n$ such that $n \lg(n) \leq 10^6$.

The simplest but the longest one is substitution. Are there some elegant ways to solve this?

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 $n_{\text{max}}$.

We just solve $x \log x = 10^6$ and round down. This sort of equation typically does not have a closed form solution (so what, closed form solutions are so 18th century, we've got computers now), so we just feed this into a computer and we get $n \approx 87847.5$, so the answer is 87847.

You did ask for the most elegant approach, you know, and that would be to use the right tool.

Now, you could also wonder how you would compute this by hand if you found yourself in the middle of a jungle. You could use the iteration method (is this what you called substitution?). Write the equation in the form of a fixed point:
$$x = \frac{10^6}{\log x}$$
Start with any initial guess for $x$ and keep applying the right-hand side. With some luck, you converge. You find a python in the jungle and make it compute:

>>> import math
>>> x = 42
>>> for i in range(20):
...    print x
...    x = 1000000.0/math.log(x)
... 
42
267546.386419
80018.8957423
88573.8173924
87784.0460781
87853.1196966
87847.0493964
87847.5826391
87847.5357949
87847.5399101
87847.5395486
87847.5395803
87847.5395775
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

That was kind of slow. A better method would be Newton's method. We are looking for the root of $f(x) = x \log x - 10^6$. The derivative is $f'(x) = 1 + \log x$ so the Newton's method step is
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n \log x_n - 10^6}{1 + \log x_n}.$$
So now we get:

>>> x = 42
>>> for i in range(10):
...     print (x)
...     x = x - (x * math.log(x) - 1000000.0)/(1 + math.log(x))
... 
42
211083.102152
91333.5177989
87852.9643949
87847.5395913
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

Much better.

StackExchange Computer Science Q#12380, answer score: 7