2
$\begingroup$

If I terminate the greedy algorithm for Egyptian fractions (i.e. http://en.wikipedia.org/wiki/Greedy_algorithm_for_Egyptian_fractions) after $n$ steps for a real (especially an irrational) number, is there a formula for the error or a description of the convergence?

Alternatively, are there ways of describing/bounds/functions for how the denominators grow? Computing about 20 random examples leads me to believe that the denominators grow at something like $n=O(\log(\log(d_n)))$.

$\endgroup$
  • $\begingroup$ A simple bound, due to the greedy part of the algorithm, is: if the latest term is $\frac{1}{n}$, then the error is less than $\frac{1}{n-1}-\frac{1}{n}=\frac{1}{n(n-1)}$. $\endgroup$ – vadim123 Dec 19 '13 at 19:58
2
$\begingroup$

Let $u$ be the number you are trying to approximate, and let $u_n$ be the error after the $n^{th}$ iteration ($u_0=u$). Let $k\in\Bbb N$ such that $\frac1k\le u_n\lt\frac1{k-1}$ (i.e. $k=\lceil u_n^{-1}\rceil$). Then, at the maximum, $u_{n+1}=\frac{1}{k-1}-\epsilon-\frac1k$ so $$u_{n+1}<\frac{1}{k(k-1)}=\frac1{\lceil u_n^{-1}\rceil(\lceil u_n^{-1}\rceil-1)}\le\frac{u_n}{\frac{1}{u_n}-1}=\frac{u_n^2}{1-u_n}=u_n\left(\frac1{1-u_n}-1\right)$$

So, if you want a strong bound, you can use $k$, but if you want a nice recursion, use that last equation (note that $u_{n+1}<u_n$ only if $u_n<\frac12$ using that last equation).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.