Small Numerators
Small Numerators
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.
Numerator 3
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
Numerator 4
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[3]/Log[4]) ~= x^0.7925 terms.
Modular Conditions
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.
Particular Values
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