Egyptian fractions with very large denominators

It is well-known that if we have a fraction $\frac ab$, with $a,b\in\mathbb N$ and $a<b$, if we apply the greedy algorithm in order to express it as a sum of unit fractions, then we may get fractions with very large denominators. For instance, if we apply the algorithm to $\frac5{31}$, what we get is$$\frac17+\frac1{55}+\frac1{3\,979}+\frac1{23\,744\,683}+\frac1{1\,127\,619\,917\,796\,295}$$and if we apply it to $\frac{1\,197}{2\,273}$, then the decimal representation of the last denominator has $14\,583$ digits. All this suggests that the following statement is true:

If $R>0$, then there are natural numbers $a$ and $b$ such that $a<b$ and that, if we apply the greedy algorithm to express $\frac ab$ as the sum of unit fractions, then one of the unit fractions $\frac1D$ that we get in that expression will be such that $\frac Db>R$.

My guess is that either this statement has already been proved or that it has already been stated as a conjecture. It that's so, can someone please provide a reference?

Solution 1:

There's a very simple answer to the original question. The greedy algorithm, applied to $a/b=2/(2n-1)$, gives $${2\over2n-1}={1\over n}+{1\over n(2n-1)}$$ so in the notation of the original question we have $${D\over b}={n(2n-1)\over2n-1}=n$$ which can be made arbitrarily large.

Solution 2:

I know this is an old question which already has an answer, but it is still interesting to try to maximize $D$, in terms of $a$ and $b$. By the greedy algorithm, we get $\frac{a}{b} = \frac{1}{\left \lceil \frac{b}{a} \right \rceil} + \frac{a \left \lceil \frac{b}{a} \right \rceil - b}{b \left \lceil \frac{b}{a} \right \rceil}$.

Since $a \left \lceil \frac{b}{a} \right \rceil - b$ (which is the numerator of the latter fraction) is strictly smaller than $a$, we know the greedy algorithm terminates in at most $a-1$ steps. If it takes exactly $a-1$ steps, then by induction we see $D = D_{a-1}$, where $D_0 = b$ and $D_i = D_{i-1} \left \lceil \frac{D_{i-1}}{a-i+1} \right \rceil$ for $1 \le i \le a-1$.

By Corollary 2 of this paper (which was referenced by Gerry Myerson in the comments), for every $a \in \mathbb{N}$ there are infinitely many $b > a$ such that the greedy algorithm applied to the fraction $\frac{a}{b}$ does indeed take $a-1$ steps to terminate. Assume $\frac{a}{b}$ is such a fraction with $a > 1$. Since $D_i = D_{i-1} \left \lceil \frac{D_{i-1}}{a-i+1} \right \rceil > \frac{D_{i-1}^2}{a}$, by induction this gives us $D = D_{a-1} > b\left(\frac{b}{a} \right)^{2^{a-1}-1}$. This means that if we fix $a$, then there is a constant $c = c(a) > 0$ such that there are infinitely many $b$ with $D > cb^{2^{a-1}}$. This is essentially best possible, since we always have $D_i \le D_{i-1}^2$ implying, once again by induction, $D \le b^{2^{a-1}}$ for all fractions $\frac{a}{b}$. To summarize:

Theorem. For a fraction $\frac{a}{b}$ with $1 \le a < b$, let $D = D(a,b)$ be the largest denominator that occurs in the greedy egyptian expanion of $\frac{a}{b}$. Then $D \le b^{2^{a-1}}$. On the other hand, for every $a \in \mathbb{N}$ there is a positive constant $c = c(a)$ such that for infinitely many positive integers $b \in \mathbb{N}$ we have $D > cb^{2^{a-1}}$.