Approximation of values in [0,1] by sums of unit fractions Let $U = \{(-1)^k\cdot\frac{1}{n}: n\in\mathbb{N}, k\in\{-1,1\}\}$ be the set of positive and negative unit fractions.
For a positive integer $m\in\mathbb{N}$ and a real $x\in [0,1]$ we set $d(m,x) = \inf\{|x-\sum_{i=1}^m u_i|: u_i \in U \textrm{ for all } i\in \{1,\ldots,m\}\}$. Then let $d_m = \sup\{d(m,x): x\in[0,1]\}$.
Is there an explicit formula for the $d_m$'s, or maybe an approximation from above or below?
 A: You can easily improve the trivial upper bound $d_m \leq \frac{1}{m}$ to $d_m \leq \frac{1}{2^{m+1}}$. You only need the first $m$ unit fractions of the series $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{16}$, $\frac{1}{32}$,... for this.
But there are better bounds. The following greedy algorithm will approximate $x$ very fast:
Start with the unit fraction closest to $x$. This will be at most $\frac{1}{4}$ away from $x$, so $d_1 = \frac{1}{4}$. (The worst case occurs for $x = 0.75$.) Then compute the distance $r$ that remains between your approximation and the target. If $r$ is equal to a unit fraction, add this unit fraction to your approximation and you are done. Otherwise, determine the $k$, for which $\frac{1}{k+1} < r < \frac{1}{k}$. Add either $\frac{1}{k+1}$ or $\frac{1}{k}$ to your approximation; pick the fraction that brings you closer to the target. As $\frac{1}{k} - \frac{1}{k+1} = \frac{1}{k(k+1)}$, your new remaining distance $r$ will now be less than $\frac{1}{2k(k+1)}$.
The approximation will thus converge extremely fast:
$d_2 \le \frac{1}{2*4*5} = \frac{1}{40}$
$d_3 \le \frac{1}{2*40*41} = \frac{1}{3820}$
...
$d_{m+1} \le \frac{1}{2} * \frac{d_m^2}{1+d_m}$
In particular, $d_{m+1} < d_m^2$, which leads to a quick convergence.
