4
$\begingroup$

I compared the two best known algorithms for Egyptian fraction expansion:

On each step for a fraction $p_n/q_n$ we choose a denominator $a_n$ such that:

$$\frac{p_n}{q_n}-\frac{1}{a_n} \geq 0, \quad \frac{p_n}{q_n}-\frac{1}{a_n-1} < 0$$

$$\frac{p_{n+1}}{q_{n+1}}=\frac{a_n p_n-q_n}{q_n a_n}$$

On each step for a fraction $p_n/q_n$ we choose a multiplier $m_n$ such that:

$$\frac{m_n p_n}{q_n} \geq 1, \quad \frac{(m_n-1)p_n}{q_n} < 1$$

(In other words, these are the exact same inequalities as in the previous case).

Then we represent:

$$\frac{p_n}{q_n}=\frac{1}{m_n}\frac{m_np_n}{q_n}=\frac{1}{m_n} \left(1+\frac{m_np_n-q_n}{q_n} \right)$$

$$\frac{p_{n+1}}{q_{n+1}}=\frac{m_np_n-q_n}{q_n}$$

This is the only difference between the methods - the fractions we work with on the next step are different. However, the denominators in this case are defined as the product of $m_k$, so I don't see why they are different from the greedy algorithm at all.

But the fact is: the second method almost always gives better results in terms of the maximum denominator size. I can't figure out why.

One famous exapmle (I give a list of denominators for each expansion):

$\frac{5}{121}=$ {25, 757, 763309, 873960180913, 1527612795642093418846225} (greedy)

={25, 25 * 31, 25 * 31 * 41, 25 * 31 * 41 * 61, 25 * 31 * 41 * 61 * 121}

={25, 775, 31775, 1938275, 234531275} (Engel)

We can see that after the first one all the other denominators are different and much smaller in the Engel case.


Below I will only write the final (multiplied) version of the denominators for the Engel expansions:

$\frac{18}{23}=$ {2, 4, 31, 2852} (greedy)

$=$ {2, 4, 32, 736} (Engel)

$\frac{41}{182}=$ {5, 40, 3640} (greedy)

$=$ {5, 40, 3640} (Engel)

$\frac{3}{37}=$ {13, 241, 115921} (greedy)

$=$ {13, 247, 9139} (Engel)

$\frac{10}{39}=$ {4, 156} (greedy)

$=$ {4, 156} (Engel)

$\frac{5}{122}=$ {25, 1017, 3101850} (greedy)

$=$ {25, 1025, 125050} (Engel)

$\frac{5}{22}=$ {5, 37, 4070} (greedy)

$=$ {5, 40, 440} (Engel)

$\frac{31}{311}=$ {11, 115, 13567, 190623619, 37683192230798623, 1474639245038064805618553239385819} (greedy)

$=$ {11, 121, 2057, 53482, 16632902} (Engel)

$\frac{21}{23}=$ {2, 3, 13, 359, 644046} (greedy)

$=$ {2, 4, 8, 32, 160, 1920, 44160} (Engel)


In other words, we have some cases where the expansions are the same, but in most cases Engel is better.

To tell the truth I encountered a case where Engel gave larger denominators, but I can't remember it now. Still, I think it was more of an exception.


A relevant paper: How many points have the same Engel and Sylvester expansions?

$\endgroup$
2
$\begingroup$

The first step in the greedy algorithm and the Engel expansion is always the same, after that, the two may start to differ. Let's start with $\dfrac{p_1}{q_1} \in (0,1)$ and suppose

$$\frac{1}{e_1} < \frac{p_1}{q_1} < \frac{1}{e_1-1}.$$

Let $p_2 = e_1p_1 - q_1$ the numerator of the next fraction we consider in the expansions. In the Engel expansion, we next look at the fraction $\dfrac{p_2}{q_1}$, and in the greedy algorithm we next look at $\dfrac{p_2}{e_1q_1}$. Our next factor in the Engel expansion is $e_2 \in \mathbb{N}\setminus \{0\}$ such that

$$\frac{1}{e_2} \leqslant \frac{p_2}{q_1} < \frac{1}{e_2 - 1}.$$

Multiplying through with $1/e_1$, the inequality is

$$\frac{1}{e_1e_2} \leqslant \frac{p_2}{e_1q_1} < \frac{1}{e_1(e_2-1)}.$$

Now $e_1 > 1$, so there are unit fractions strictly between the two bounds,

$$\frac{1}{e_1e_2} < \frac{1}{e_1e_2 - 1} < \frac{1}{e_1e_2 - 2} < \dotsc < \frac{1}{e_1(e_2-1)+1} < \frac{1}{e_1(e_2-1)},$$

and the second fraction in the greedy algorithm coincides with the second fraction from the Engel expansion if and only if

$$\frac{1}{e_1e_2} \leqslant \frac{p_2}{e_1q_1} < \frac{1}{e_1e_2 - 1}.$$

That does happen, but of course not always. If the second fractions obtained with both algorithms coincide, and the expansion is not yet complete, in the next step we have the same situation (with different numbers), in the Engel expansion we look at $\dfrac{p_3}{q_1}$, where $p_3 = e_2p_2-q_1$, and in the greedy algorithm we look at $\dfrac{p_3}{(e_1e_2)q_1}$. Then the Engel expansion next produces the denominator $(e_1e_2)e_3$ and the greedy algorithm the denominator $(e_1e_2)e_3 - k$, where $0 \leqslant k < e_3$. Note that the denominator of the first different unit fraction - if any - that we obtain via the Engel expansion is larger than the corresponding denominator from the greedy algorithm. The algorithms produce different Egyptian fraction expansions because the Engel algorithm produces a chain of denominators where every denominator divides the next, while no such restriction holds for the greedy algorithm.

To see why the Engel expansion often yields much smaller denominators than the greedy algorithm, note that in the Engel expansion the denominator of the fraction we consider to determine the next Engel factor never grows. When we consider the fraction $\dfrac{p_n}{q_n}$ and obtain the factor $e_n$, which we suppose doesn't yet terminate the algorithm, the next fraction considered is the reduced form of $\dfrac{e_np_n - q_n}{q_n}$, and its denominator $q_{n+1}$ is either $q_n$ or a proper divisor of $q_n$. Except for the last step, where we consider the fraction $\dfrac{1}{q_\ell}$, we always consider a fraction $\dfrac{p_n}{q_n}$ with $p_n \geqslant 2$, so we have

$$e_n-1 < \frac{q_n}{2}\quad\text{or}\quad e_n \leqslant \biggl\lceil\frac{q_n}{2}\biggr\rceil.$$

If we expand the fraction $\dfrac{p}{q}$, that means the $n^{\text{th}}$ denominator $a_n = e_1\cdot\dotsc\cdot e_n$ satisfies

$$a_n \leqslant \biggl\lceil\frac{q}{2}\biggr\rfloor^n$$

except possibly for the last denominator where we may have $e_{\ell} = q$. In any case, we have

$$a_n \leqslant 2\cdot \biggl\lceil\frac{q}{2}\biggr\rfloor^n,$$

so the denominators obtained via the Engel expansion grow at most exponentially.

In the greedy algorithm on the other hand, the denominators of the considered fractions can grow, and they can grow quite fast, and that leads to the possibility of very large denominators occurring quickly. At a step before the greedy algorithm ends, we have

$$\frac{1}{a_n} < \frac{p_n}{q_n} < \frac{1}{a_n-1}$$

and consequently

$$0 < \frac{p_{n+1}}{q_{n+1}} = \frac{a_n p_n - q_n}{a_n q_n} < \frac{1}{a_n-1} - \frac{1}{a_n} = \frac{1}{a_n(a_n-1)},$$

so we have $a_{n+1} > a_n(a_n-1)$. Considering only $\dfrac{p}{q} \in (0,1)$ to avoid initial $\frac{1}{1}$ in the expansion, in the greedy algorithm we have $a_1 \geqslant 2$ and $a_{n+1} - \frac{1}{2} > \bigl(a_n - \frac{1}{2}\bigr)^2$, which yields a lower bound of

$$a_n \geqslant \biggl(\frac{3}{2}\biggr)^{\bigl(2^{n-1}\bigr)} + \frac{1}{2}.$$

So the denominators in the greedy algorithm grow at least as fast as the composition of two exponentials. Unless the greedy algorithm yields a short expansion or the Engel algorithm yields a very long expansion, the at most geometric growth of the denominators obtained through Engel expansion is dwarfed by the superexponential growth of the denominators obtained in the greedy algorithm.

But for fractions where the greedy algorithm yields a short expansion, the Engel algorithm can yield much larger denominators. The smallest (in the sense of smallest denominator and numerator) example is $\dfrac{5}{6}$, where the greedy algorithm gives $\dfrac{5}{6} = \dfrac{1}{2} + \dfrac{1}{3}$, while the Engel algorithm yields $\dfrac{5}{6} = \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{12}$. A more striking example is $\dfrac{73}{366}$, where the greedy algorithm yields $\dfrac{73}{366} = \dfrac{1}{6} + \dfrac{1}{31} + \dfrac{1}{1891}$, while the Engel algorithm yields

$$\frac{73}{366} = \frac{1}{6} + \frac{1}{36} + \frac{1}{216} + \frac{1}{2808} + \frac{1}{44928} + \frac{1}{943488} + \frac{1}{29248128} + \frac{1}{1784135808}.$$

Ouch!

Let's look why the Engel algorithm loses so spectacularly here. We can formulate the algorithm to obtain an Egyptian fraction expansion of $\dfrac{p}{q}$ as

  1. Let $m = \biggl\lceil\dfrac{q}{p}\biggr\rceil$, output $\dfrac{1}{m}$.
  2. Let $\tilde{p} = m\cdot p - q$. If $\tilde{p} = 0$, stop. Else expand $\dfrac{\tilde{p}}{q}$ (reducing the fraction lets one work with smaller numbers, but is not really necessary here) using this algorithm and multiply all denominators of the resulting expansion by $m$.

In the example above, we get

$$E\biggl(\frac{73}{366}\biggr) = \frac{1}{6} + \frac{1}{6}\cdot E\biggl(\frac{6\cdot 73 - 366}{366}\biggr) = \frac{1}{6} + \frac{1}{6}\cdot E\biggl(\frac{72}{366}\biggr) = \frac{1}{6} + \frac{1}{6}\cdot E\biggl(\frac{12}{61}\biggr).$$

Now we see that the multiplying denominator $6$ and the numerator $12$ of the next fraction to expand are not coprime. Per the algorithm, we do not simplify and expand $\dfrac{12}{61}$. That has a pretty bad expansion for both algorithms and thus leads to the above expansion. If we simplify and rewrite $\dfrac{1}{6}\cdot E\biggl(\dfrac{12}{61}\biggr)$ to $E\biggl(\dfrac{2}{61}\biggr)$, which is mathematically valid of course, we get $\dfrac{2}{61} = \dfrac{1}{31} + \dfrac{1}{1891}$, and the much nicer expansion that the greedy algorithm yields.

This suggests that we may get expansions with smaller denominators if we modify the Engel algorithm to simplify in such cases. The modified algorithm is

  1. Let $m = \biggl\lceil\dfrac{q}{p}\biggr\rceil$, output $\dfrac{1}{m}$.
  2. Let $\tilde{p} = m\cdot p - q$. If $\tilde{p} = 0$, stop. Else let $\dfrac{\hat{p}}{\hat{q}}$ the reduced form of $\dfrac{\tilde{p}}{q}$, let $\dfrac{p'}{m'}$ the reduced form of $\dfrac{\hat{p}}{m}$, expand $\dfrac{p'}{\hat{q}}$ using this algorithm and multiply all denominators of the resulting expansion by $m'$.

The modification pushes the algorithm in the direction of the greedy algorithm whenever $\tilde{p}$ and $m$ aren't coprime. That opens it to a weaker form of the risk of the greedy algorithm that a unit fraction is used that is too close to the fraction to expand for the next unit fraction to have a small(ish) denominator. We still have the growth bounds for the denominators that hold for the Engel algorithm, but it can happen that $\dfrac{p'}{q}$ has a longer expansion than $\dfrac{\tilde{p}}{q}$, leading to an overall expansion with larger denominators. But it seems plausible that this is a rare occurrence.

Testing on fractions $\dfrac{p}{q}$ with $2 \leqslant p < q \leqslant 100$ and $\gcd(p,q) = 1$, the modified algorithm does in the majority of cases yield the "better" of the expansions obtained by the greedy algorithm or the Engel algorithm, in some cases (roughly $5\%$) the modified algorithm produces an expansion whose largest denominator is smaller than that obtained from either the greedy or the Engel algorithm, and in few cases (about $0.6\%$) it produces an expansion whose largest denominator is larger than that produce by either of the other two algorithms. For larger $p,q$ the expansions will generally become longer, so there will be more opportunity for the modified algorithm to differ from the Engel algorithm without producing the same expansion as the greedy algorithm. Nevertheless, I expect that it will continue to be at least as good as the greedy and the Engel algorithm for most inputs, strictly better (measured by largest denominator produced) in a non-negligible number of cases, and only rarely strictly worse than both. I dare not predict numbers, however.

Another variation of the algorithm doesn't only use the current factor to simplify the fraction but also the previously determined factors. This leads to more simplifications occurring. According to my tests with small $p,q$, that more often leads to an expansion with smaller denominators than to one with larger denominators, and makes it the overall best of the four algorithms at least for smallish $p,q$. But I expect that will also be the case in general. (I make no promises, though, I guessed wrong before.) The algorithm is as follows: To expand the fraction $\dfrac{p}{q}$ with multiplier $m$,

  1. Let $a = \biggl\lceil\dfrac{q}{p}\biggr\rceil$, output $\dfrac{1}{am}$.
  2. Let $\tilde{p} = ap-q$. If $\tilde{p} = 0$, stop. Else let $\dfrac{\hat{p}}{\hat{q}}$ the reduced form of $\dfrac{\tilde{p}}{q}$, let $\dfrac{p'}{m'}$ the reduced form of $\dfrac{\hat{p}}{am}$ and expand $\dfrac{p'}{\hat{q}}$ with multiplier $m'$ using this algorithm.

Some fun expansions (svariant is the first modification and variant is the last algorithm mentioned above; the names suck, but as is well-known, naming is the hardest thing in computer science):

*Egyptian> greedy 113 355
[4,15,609,864780]
*Egyptian> engel 113 355
[4,16,176,7920,562320]
*Egyptian> svariant 113 355
[4,16,176,7920,562320]
*Egyptian> variant 113 355
[4,16,176,7810]
*Egyptian> greedy 53 75
[2,5,150]
*Egyptian> engel 53 75
[2,6,30,150]
*Egyptian> svariant 53 75
[2,6,26,650]
*Egyptian> variant 53 75
[2,6,25]
*Egyptian> greedy 63 76
[2,4,13,494]
*Egyptian> engel 63 76
[2,4,16,64,1216]
*Egyptian> svariant 63 76
[2,4,14,140,2660]
*Egyptian> variant 63 76
[2,4,14,133]
*Egyptian> greedy 44 59
[2,5,22,3245]
*Egyptian> engel 44 59
[2,6,18,54,216,2592,152928]
*Egyptian> svariant 44 59
[2,6,18,54,216,2592,152928]
*Egyptian> variant 44 59
[2,6,15,90,810,12150,716850]
*Egyptian> greedy 49 66
[2,5,24,1320]
*Egyptian> engel 49 66
[2,6,18,54,594]
*Egyptian> svariant 49 66
[2,5,25,425,14025]
*Egyptian> variant 49 66
[2,5,25,425,14025]
*Egyptian> greedy 73 99
[2,5,27,2970]
*Egyptian> engel 73 99
[2,6,18,72,792]
*Egyptian> svariant 73 99
[2,6,18,66]
*Egyptian> variant 73 99
[2,6,15,255,8415]

I particularly like the cases $\dfrac{53}{75}$, $\dfrac{63}{76}$, and $\dfrac{73}{99}$ since all four algorithms produce different Egyptian fraction expansions for them. These examples illustrate that simplifying can have huge benefits, but it can also incur a significant penalty.

I note in passing that you stopped the greedy expansion of $\dfrac{31}{311}$ short, the greedy algorithm gives an expansion with ten unit fractions, the largest denominator having 537 digits.


Code (Haskell, unoptimised) for those who want to play:

module Egyptian where

greedy :: Integer -> Integer -> [Integer]
greedy 0 _ = []
greedy p q = case quotRem q' p' of
               (m,0) -> [m]
               (m,_) -> let a = m+1 in a : greedy (a*p-q) (a*q)
  where
    (p',q') = case gcd q p of
                1 -> (p,q)
                g -> (p `quot` g , q `quot` g)

engel :: Integer -> Integer -> [Integer]
engel 0 _ = []
engel p q = case quotRem q' p' of
              (m,0) -> [m]
              (m,_) -> let a = m+1 in a : map (*a) (engel (a*p-q) q)
  where
    (p',q') = case gcd q p of
                1 -> (p,q)
                g -> (p `quot` g , q `quot` g)

variant :: Integer -> Integer -> [Integer]
variant p q = go 1 p' q'
  where
    (p',q') = case gcd q p of
                1 -> (p,q)
                g -> (p `quot` g , q `quot` g)
    go m 1 b = [m*b]
    go m a b = m' : go m'' a''' b'
      where
        e = 1 + (b `quot` a)
        a' = a*e - b
        g = gcd b a'
        a'' = a' `quot` g
        b' = b `quot` g
        m' = m*e
        g' = gcd m' a''
        a''' = a'' `quot` g'
        m'' = m' `quot` g'

svariant :: Integer -> Integer -> [Integer]
svariant p q = go 1 p' q'
  where
    (p',q') = case gcd q p of
                1 -> (p,q)
                g -> (p `quot` g , q `quot` g)
    go m 1 b = [m*b]
    go m a b = (m*e) : go m' a''' b'
      where
        e = 1 + (b `quot` a)
        a' = a*e - b
        g = gcd b a'
        a'' = a' `quot` g
        b' = b `quot` g
        g' = gcd e a''
        e' = e `quot` g'
        m' = m*e'
        a''' = a'' `quot` g'
$\endgroup$
5
  • $\begingroup$ This is an excellent answer, thank you! Checking for divisibility is a difficult procedure to implement in an algorithm (not counting build-in functions of course, but they can still be slow for large numbers), but necessary in this case. And thank you for the new algorithms! Turns out that $73/366$ and your other examples can't be tackled by some of the 'best' algorithms I found so far. (without getting long and bad expansions). $\endgroup$ – Yuriy S Feb 6 '17 at 17:25
  • $\begingroup$ As for the mistake with 31/311, I just hadn't noticed because my algorithm had a 'safety feature' and it stopped once $p_n/q_n$ became too small $\endgroup$ – Yuriy S Feb 6 '17 at 17:28
  • $\begingroup$ $\dfrac{233}{987}$, $\dfrac{610}{987}$, $\dfrac{706}{987}$ and $\dfrac{712}{987}$ are also interesting. Again all algorithms give different expansions. $\endgroup$ – Daniel Fischer Feb 6 '17 at 23:10
  • $\begingroup$ Curious. Unfortunately, I don't know Haskell, so I can't try your algorithm without rewriting it first for Mathematica. Still, checking with some methods I found the best expansion for $\frac{706}{987}$ as {2, 8, 14, 56, 987}, using my 'splitting-joining algorithm' $\endgroup$ – Yuriy S Feb 7 '17 at 0:04
  • $\begingroup$ The second modified algorithm produces [2,6,21,987]. The first modified algorithm gives [2,6,22,330,6930,325710], which is far less good. $\endgroup$ – Daniel Fischer Feb 7 '17 at 13:41

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.