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
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
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