Algorithms for Egyptian Fractions

o Conflict Resolution Methods

We next examine two methods for Egyptian fraction representation that employ the following simple idea: from a fraction x/y we can form a representation in unit fractions by making x copies of 1/y. This is not an Egyptian fraction since the unit fractions are not distinct. However we can now search for conflicting pairs (two copies of the same fraction) and resolve the conflict by replacing the pair with some other fractions adding to the same value. The methods differ in the way they choose the replacement fractions. It is trivial to prove that such methods give correct representations, but it may be harder to prove that they always halt or to analyze how well they perform.

+ The Pairing Method

This method uses the conflict resolution idea above. Whenever we have a conflicting pair (two copies of some fraction 1/y), we replace them either by a single fraction 2/y if y is even, or by 2/(y+1)+2/(y(y+1)) if y is odd. (Note that in all cases, the fractions simplify to have unit numerators.) The order in which this is done does not matter. Note that this process may combine pairs of fractions to form integers; e.g. this happens with sufficiently many copies of 1/7. If this happens, we allow integers to be combined to make larger integers. This type of method is a natural fit to the pattern-matching capabilities of Mathematica, so our implementation defines a function DoPairing in such a way that Mathematica repeatedly transforms its argument list using the replacement defined above. 


DoPairing[p___,q:Rational[1,y_],q_,r___] :=
	If[OddQ[y], DoPairing[p,2/(y+1), 2/(y(y+1)),r],
				DoPairing[p,2/y,r]];
DoPairing[p___,q_Integer,r_Integer,s___] :=
    DoPairing[p,q+r,s];
		
SetAttributes[DoPairing, Orderless];

EgyptPairList[l_] := Reverse[List @@ DoPairing @@ l];
EgyptPairing[Rational[x_,y_]] :=
   	EgyptPairList[Table[1/y, {x}]]

Each replacement of 1/y+1/y by 2/y reduces the number of terms, initially x, by one, which can happen at most x times. Each other replacement leaves the number of terms the same but reduces the list of terms in lexicographic order; one can only perform such reductions a finite number of times. Therefore the algorithm eventually halts, with a representation having at most x terms.

Next let us determine the largest denominator that can arise. One of the fractions must be at least 1/y, and in general if the remainder after the first few terms is a/b, the next largest fraction in the representation must be at least a/xb. So if we remove the fractions from the final representation in order by size, then at each step the denominator is at most increased to its square times x, and the largest denominator is at most (xy)^(2^x). But this seems somewhat pessimistic ­­ with the heuristic assumption that equal fractions are not usually generated from different starting pairs, we get at most x replacements and in this case the largest denominator is roughly y^x (or even fewer if some denominators of intermediate terms are divisible by two). 


EgyptPairing[18/23]

 1  1  1   1    1    1
{-, -, --, --, ---, ----}
 2  6  12  35  276  2415

Perhaps more important than the direct use of this method for finding Egyptian fractions is the following fact, which shows that if we want to find a representation with few terms, it suffices to represent the given number as a sum of unit fractions without worrying about distinctness.

Theorem: Let q be represented as a sum of t unit fractions, not necessarily distinct. Then q has a t-term Egyptian fraction representation.

Proof: apply the function EgyptPairList defined above to the given representation. Each step leaves the sum of the fractions unchanged, and either shrinks the list by one fraction or leaves its length unchanged. The fact that this halts can be shown by the same argument given for the termination of EgyptPairing.

Stefan Bartels has informed me that this was first proven by Tanzo Takenouchi [Tak21]. It would be of interest to bound the number of replacement steps performed by EgyptPairList and EgyptPairing.

+ The Splitting Method

The next method we describe is similar to the pairing method, but less clever: we keep a list of unit fractions as before, and resolve conflicts by replacing fractions with smaller fractions adding to the same quantity. However, instead of replacing 2/y with 2/(y+1) + 2/(y(y+1)), we replace it with 1/y + 1/(y+1) + 1/(y(y+1)). In other words, when two fractions conflict, we leave one of them in place and split the other one, creating a list with one more fraction than before. 


DoSplitting[p___,q:Rational[1,y_],q_,r___] :=
	DoSplitting[p,q,1/(y+1),1/(y(y+1)),r];
		
SetAttributes[DoSplitting, Orderless];

EgyptSplitting[Rational[x_,y_]] :=
   	Reverse[List @@ DoSplitting @@ Table[1/y, {x}]]

It is not obvious that this method halts, but this has been proven by Graham and Jewett [Wag91]; see also Beeckmans [Bee93]. If no fraction arises in two different ways (once as 1/(y+1) and once as 1/(y(y+1)), we could analyze the algorithm on input x/y as having x-1 levels of splitting, each of which essentially doubles the number of terms in the representation. The total number of terms produced would then be O(2^x), and the largest denominator would be O(y^(2^x)). This is a best-case analysis; in practice the results will be even worse. 


EgyptSplitting[5/6]

 1  1  1  1  1   1   1   1   1   1   1   1   1   1   1
{-, -, -, -, --, --, --, --, --, --, --, --, --, --, --, 
 6  7  8  9  10  42  43  44  45  56  57  58  72  73  90
 
   1     1     1     1     1     1     1     1     1
  ----, ----, ----, ----, ----, ----, ----, ----, ----, 
  1806  1807  1808  1892  1893  1980  3192  3193  3306
 
   1       1        1        1        1        1
  ----, -------, -------, -------, -------, --------, 
  5256  3263442  3263443  3267056  3581556  10192056
 
        1
  --------------}
  10650056950806

Egyptian Fractions, Number Theory, David Eppstein, ICS, UC Irvine

Formatted by nb2html and filter. Last update: .