# Finding the nearest integers to real numbers defined implicitly

I was trying to bound the maximum cost of top-down merge sort: $$f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1,$$ where $\lg n$ is the binary logarithm of $n$ and $\lceil{x}\rceil$ is the smallest integer greater than or equal to $x$. Let $\{x\}$ be the fractional part of $x$. I made two cases:

• If $n=2^p$, then $f(n) = n\lg n - n + 1$;
• else $\lceil\lg n\rceil = \lg n -\{\lg n\}+1$ and $f(n) = n\lg n + \theta(1-\{\lg n\}) \cdot n + 1$, with $\theta(x) := x - 2^x$. The derivative of $\theta$ shows that $\max_{0<x\leqslant 1}\theta(x) = -(1+\ln\ln{2})/\!\ln{2} \simeq -0.9139$ and $\min_{0<x\leqslant 1}\theta(x) = \theta(1) = -1$.

So we have $n\lg n - n + 1 \leqslant f(n) < n\lg n - 0.91 n + 1.$ Considering $\theta(1-\{\lg n\})$ again, the lower bound is tight if $\{\lg n\} = 0$ or, equivalently, $n=2^p$.

What I want is to characterise the $n$ for which $f(n)$ is the closest to the upper bound: $\theta'(x) = 0 \Leftrightarrow x = -\lg\ln 2$, so $\theta'(1-\{\lg n\}) = 0 \Leftrightarrow \{\lg n\} = 1 + \lg\ln 2$.

How can I characterise the natural numbers $n$ such that $\{\lg n\}$ is as close as possible to $1 + \lg\ln 2$? For instance, could it be $n=2^p-1$? $2^p+1$?

EDIT In the comments, the real solution is $2^k\ln 2$, which raises the question of the integer solution. Assuming that the nearest integer is the solution, the first values for $k=1$ to $12$ are $2$, $3$, $6$, $11$, $22$, $44$, $89$, $177$, $355$, $710$, $1420$, $2839$. Is the assumption right? What is the general term?

-
lg? What's lg?? – Gerry Myerson Sep 21 '12 at 13:01
It is the binary logarithm. I am a computer scientist and the notation $\lg n$ is often preferred to $\log_2 x$, due to its frequency. – Christian Sep 21 '12 at 16:08
Ross Millikan's comment suggests taking $n = 2^p \ln 2$ rounded to the nearest integer. Certainly within any given dyadic interval $[2^k,2^{k+1})$ this will be the best (if we round a bit more judiciously). Are you asking for the rare cases where this approximation is much better than average? – Erick Wong Sep 21 '12 at 16:30
I would like an answer in the form $n=2^p+k$, where $p$ is a positive integer and $k$ is an integer. – Christian Sep 21 '12 at 16:54

I don't think your $x$ is well defined. $1+ \lg \ln 2 \approx = 0.47123$ but there are many $x$'s to choose from. Note that $2^{(1+ \lg \ln 2)}=2 \ln 2$, so $x=2 \ln 2$ is a solution with the nearest integer being $1$, but so is $x=2^{10} \ln 2\approx 709.78271289$ with the nearest integer being $710$
@Christian: you have said $x=2^n \ln 2$ for some natural $n$. For a given one, you can check whether $\{(n-1) \ln 2\}$ is greater or less than $0.5$. If you look through the $n$'s, you should be able to get as close to an integer as you like. I don't really understand what you are asking. – Ross Millikan Sep 12 '12 at 15:43
I think Ross has answered your question, but I'll try a different way to present it. If the fractional part of $\log_2n$ is close to $1+\log_2\log 2$, that says $\log_2n$ is close to $m+\log_2\log 2$ for some integer $m$, which says $n$ is close to $2^m\log2$ for some integer $m$. I doubt there's any way to characterize those integers $m$ for which $2^m\log2$ is close to an integer.