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$
1
  • $\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, 2013 at 19:58

1 Answer 1

Reset to default
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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .