The algorithms described above work for any input. We now discuss techniques limited to specific numerators. The typical question here is how many terms are needed to represent fractions with a given numerator. For fractions 2/y the answer is clearly 2. Some fractions 3/y require 3 terms, as we see below. It is not known whether any fraction 4/y requires 4 terms.
More generally, good bounds are known on the number of terms needed to represent x/y measured as a function of y [Vos85], but there seems to be less work on measuring this minimum number of terms as a function only of x. As we note in the section on 4/y, a solution to this specific case would have implications for the general problem.
The basic result for fractions of the form 3/y is that there is a two-term expansion if and only if y has a factor congruent to 2 mod 3. Klee and Wagon [KW91] credit this result to N. Nakayama; however they supply no citation, so we repeat the proof below.
Theorem: 3/y has a two-term expansion if and only if y has a factor congruent to 2 mod 3.
Proof: In one direction, the representation 3/(3n+2)=1/(n+1)+1/(n+1)(3n+2) is found by both the greedy and continued fraction methods. This idea can easily be extended to 3/y where y is a multiple of 3n+2. In the other direction, suppose y=3n+1 and 3/y=1/a+1/b=(a+b)/ab. First note that a and b must be divisible by the same power of 3, since if a were divisible by 3^i and b by 3^j, with j>i, then a+b would not divisible by 3^j and the powers of 3 wouldn't cancel from the denominator. Let g=gcd(a,b), u=a/g, v=b/g, so 3/y=(u+v)/guv and 3 divides u+v; let u+v=3z. Then 1/a+1/b=3z/guv and g must factor as zw since gcd(uv,u+v)=1. So y=uvw. For u+v=3z, one of u and v (say u) must be 2 mod 3, giving the factor of y we seek.Unfortunately this seems to imply that finding short representations, even in this special case, is computationally difficult: at least as difficult as factoring integers.
The small numerator version of the reverse greedy method (which includes factorization as one of its subroutines) will always find a two-term representation for 3/n when one exists. Some examples of two-term representations that would not be found by our other general algorithms: 3/25=1/10+1/50; 3/55=1/22+1/110=1/20+1/220; 3/121=1/44+1/484
The question of whether all fractions 4/y have 3-term representations is discussed by Mordell [Mor69], who attributes it to Erdös and Straus. Guy [Guy81] cites several other authors as having worked on the problem: Bernstein, Obláth, Rosati, Shapiro, Straus, Yamamoto, and Franceschine. Others have worked on more general versions of this problem including Schinzel, Sierpinski, Sedlácek, Palamà, Stewart, Webb, Breusch, Graham, and Vaughan. A positive solution to this question would have more general implications: we could use such a solution as the basis for a conflict resolution method that, given a number x/y, would find an Egyptian fraction representation with x^(Log/Log) ~= x^0.7925 terms.
Mordell shows that in any example 4/y requiring 4 terms in an Egyptian fraction representation, y must be 1 mod 24, ±1 mod 5, and one of three values mod 7 (giving a total of 6 possible values mod 840, all squares of small numbers). If y is a minimal counterexample, it must be prime (since if y=ab we could divide all terms in a representation of 4/a by b).
If y is 2 or 3 mod 4, the greedy algorithm gives a 2 or 3 term representation. If y is 1 mod 4 we have the representation 1/ceil[y/4] + 3/(y ceil[y/4]) where the last term has a 2-term expansion whenever y is 2 mod 3 or 5 mod 8. So if 4/y is to fail to have a 3 term representation, y must be of the form 24n + 1. Several methods extend this analysis by representing 4/y when y (equivalently n) has certain values modulo small primes.
The representations 1/(6n+1) + 3/(24n+1)(6n+1) and 1/(18n+1)(24n+1) + 3/(18n+1) work if one of 6n+1, 18n+1, or 24n+1 is divisible by a prime p congruent to 5 mod 6. Thus for any of these primes one can derive rules for finding three-term representations of 4/y, that work whenever y has certain values mod p. We can use this technique to find representations when n is congruent to 4, 3, or 1 mod 5 (and so, rule out counterexamples for y congruent to anything but ±1 mod 5).
The representation 1/(6n+k) + (4k-1)/(6n+k)(24n+1) works via a greedy method if a factor of the second denominator is (4k-2) mod (4k-1), or more generally if the factor is (4k-1-i) mod (4k-1) and i divides the denominator. In particular these work with k=2 when n is 2, 3, 4, or 6 mod 7 (with the corresponding values of i being 0, 1, 1, and 2). Therefore in any counterexample 4/y, y must be a quadratic residue mod 7.
Yet another type of rule is possible: consider the decomposition 1/(6n+k) +a/(6n+k)(24n+1) + b/(6n+k)(24n+1), where a+b = 4k-1. This is only possible when k is even, since otherwise one of a or b would be even and not divide the denominator. For instance 4/(24n+1)=1/(6n+10) + 26/(6n+10)(24n+1) + 13/(6n+10)(24n+1) where the last two simplify to unit fractions if n is 7 mod 13.
As noted above, the numbers y for which 4/y might possibly require four terms fall into six classes modulo 840: 1, 121, 169, 289, 361, and 529. We only need to consider prime n since if mn is a counterexample, so must be both m and n. Following are representations for all such cases through 12500. Most use rules like the ones described above that depend only on the values of y mod 11, 13, and 19, but 4/3361 uses a method that depends on y mod 29 and 4/8089 uses a method that depends on y mod 17.
4/1801 = 1/451 + 1/295364 + 1/3249004
4/2521 = 1/636 + 1/69748 + 1/131876031
4/2689 = 1/676 + 1/139828 + 1/908882
4/3049 = 1/772 + 1/60980 + 1/5884570
4/3361 = 1/841 + 1/974690 + 1/28266010
4/3529 = 1/892 + 1/80726 + 1/569764108
4/3889 = 1/975 + 1/345150 + 1/268457670
4/4201 = 1/1096 + 1/25208 + 1/13237351
4/4561 = 1/1244 + 1/13684 + 1/15603181
4/4729 = 1/1185 + 1/510732 + 1/201739140
4/5209 = 1/1308 + 1/296262 + 1/3086457516
4/5569 = 1/1402 + 1/200484 + 1/140539284
4/5881 = 1/1604 + 1/17644 + 1/25941091
4/6841 = 1/1713 + 1/1065486 + 1/7288989726
4/7681 = 1/1924 + 1/1136788 + 1/7389122
4/8089 = 1/2023 + 1/5775546 + 1/98184282
4/8521 = 1/2324 + 1/25564 + 1/54457711
4/8689 = 1/2175 + 1/1718250 + 1/14929874250
4/8761 = 1/2196 + 1/836676 + 1/3665059218
4/8929 = 1/2233 + 1/7250348 + 1/79753828
4/9241 = 1/2314 + 1/1644898 + 1/10691837
4/9601 = 1/2406 + 1/1008105 + 1/269500070
4/9769 = 1/2452 + 1/614226 + 1/12000747588
4/10369 = 1/2828 + 1/31108 + 1/80639713
4/12049 = 1/3016 + 1/2795368 + 1/18169892
4/12289 = 1/3078 + 1/1644678 + 1/30317171913
According to Guy, N. Franceschine has performed similar calculations for y<10^8.
Egyptian Fractions, Number Theory, David Eppstein, ICS, UC Irvine
Formatted by nb2html and filter. Last update: 09 Sep 1996, 16:24:43 PDT.