1

I am given an arbitrary positive integer $s$. I want to find the smallest integer $n$ such that

$$s \leq n \log_2 n$$

where $\log_2$ is log base $2$.

Is there an efficient way to compute $n$?

Fly by Night
  • 32,272
Paul Reiners
  • 817
  • 1
    Use the Lambert W function. –  Aug 11 '15 at 18:51
  • 1
    @YiannisGalidakis Are computations with Lambert's W-function possible without the use of a computer? – Fly by Night Aug 11 '15 at 18:52
  • Don't use the Lambert W function. Use bisection instead! Start with an upper bound $n_{\rm high}=s$ and a lower bound $n_{\rm low}=1$. Then calculate $n = \frac{n_{\rm high} + n_{\rm low}}{2}$ and check if $s \leq n \log_2 n$. If it is take $n_{\rm high} = n$ and repeat. Otherwise change $n_{\rm low} = n$ and repeat. You can stop when $n_{\rm high} - n_{\rm low} < 1$. – Winther Aug 11 '15 at 18:53
  • 1
    @FlybyNight I believe that calculations with Lambert W would be extremely complicated to attempt by hand. However, computing logarithm or exponential to desired accuracy (even with integer arguments) can also be very tedious by hand. This question begs for use of a computer in one way or another. The binary search proposed by an earlier comment is probably the easiest way to go, although still requiring a computer. – user2566092 Aug 11 '15 at 18:55
  • I am using a computer. I had thought of doing binary search, but I was wondering if there is something more efficient. I'll just go ahead and do that. – Paul Reiners Aug 11 '15 at 19:02
  • It depends. For one time evaluation you could even just check every integer $n$ until $n\log_2(n) > s$. That would take no time even if $s=10000$. If you want to do this operation billions of times then one should definately use a smarter method. Bisection (binary search) is always a good method. However one can also precompute the function $s(n) = n\log(n)$ and make a spline of the inverse (this is basically Lambert W) and then use the spline-lookup to get the value. This avoids computing $\log$'s (which are expensive) all the time. – Winther Aug 11 '15 at 19:12
  • @PaulReiners For $s>4$ or so, you get a modest cost savings by replacing the lower bound with $s/\log(s)$. This works because $s/\log(s) \log(s/\log(s))=s - s \log(\log(s))/\log(s)<s$. This also means that $s(1+\log(\log(s)))/\log(s)$ is an upper bound, which will be better than $s$. – Ian Aug 11 '15 at 19:28

1 Answers1

1

$$s \leq n\log_2(n)$$ $$s \leq \frac{n\log n}{\log 2}$$ $$s\log 2 \leq n\log n$$ $$s\log 2 \leq e^{\log n}\log n$$ Using the Lambert W function and the fact that you want the smallest $n$, we have $$\log n = W\left(s\log 2\right)$$ $$n =e^{W\left(s\log 2\right)}=\frac{s\log 2}{W\left(s\log 2\right)}$$ As others have stated, you'll need a computer to evaluate this.

k170
  • 9,045