From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: Egyptian Fractions Date: 20 Apr 1999 23:15:37 -0700 Newsgroups: sci.math Keywords: background on the "4/N" problem "TimeLord" writes: > Given a whole number n, there exist three unique whole numbers, x, y, z, > such that: 4/n = 1/x + 1/y + 1/z I don't know what you mean by "unique", since usually there are many solutions for a given n. Sometimes x, y, and z are required to be unequal but it makes no essential difference (if you find a solution with some equal you can find another solution with all unequal). > How old is this conjecture? By what name is it called? I don't know. According to Mordell's book on number theory (1969) the problem is due to Erdos and Straus. I think I've occasionally seen it referred to by their names, but more often "the 4/n problem" or "the diophantine equation 4/n=1/x+1/y+1/z" etc. > Has it been proved or disproved yet? Not to my knowledge. > Where can I find a list of solutions to this formula? I have some material on it in my site on Egyptian fractions, http://www.ics.uci.edu/~eppstein/numth/egypt/ (specifically at http://www.ics.uci.edu/~eppstein/numth/egypt/smallnum.html there is a list of moduli relations which work for many n, and solutions for all n through 12500 not covered by those relations). I also have a Mathematica package which can quickly find solutions to any n -- theoretically the time is pretty near linear in n, which is exponential in the input size, but in practice one quickly finds a solution with x=(n/4)+epsilon for some small epsilon. The same package implements many other Egyptian fraction algorithms (Egypt.m on my site or at MathSource). To use it to find a solution for 4/n, type EgyptianFraction[4/n, MaxTerms->3] It seems to be slowest when 4/n=1/x+1/y already has a solution without needing a third term, so you may be best off trying MaxTerms->2 first (much faster when it works). I just tested some nine-digit numbers and typical solution times seem to be around a second in that range. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: egyptian fractions Date: 27 Apr 1999 18:20:23 -0700 Newsgroups: sci.math In <37265772.6AF66037@bellatlantic.net> Bimal writes: > I have > devised a an algorithm for quickly finding a short series of fractions > that add together to make the complex one. Your algorithm (always remove the largest possible unit fraction) is usually known as the "greedy algorithm". It can produce very ugly representations e.g. try it on 31/311. > my question is whether, for the numerators 2 through 8 inclusive, my > algorithm is the most efficient? What do you mean by most efficient? It doesn't use the fewest terms E.g. 3/25 = 1/10 + 1/50 but your algorithm produces 1/9 + 1/113 + 1/9*25*113. However, it does always use at most n terms for a fraction n/d. See my web page http://www.ics.uci.edu/~eppstein/numth/egypt/ for many other (usually better) ways of coming up with these representations. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: 4/n = 1/x + 1/y + 1/z is plausibly unsolvable Date: 24 Jun 1999 13:35:20 -0700 Newsgroups: sci.math mattb@umit.maine.edu (Matthew Burgess) writes: > 1) For ANY INTEGER n, are there 3 integers x,y,z such that: > 4/n = 1/x + 1/y + 1/z? > - It is somewhat obvious that for n = -1,0,1 this is not true Huh? -1 = 1/(-1) + 1/(-1) + 1/1 0 = 1/(-1) + 1/2 + 1/2 1 = 1/(-1) + 1/1 + 1/1 > but how about for abs(n) > 1? 3/n always has a two-term solution if you allow one term to be negative: 3/(3k) = 1/k = 1/2k + 1/2k = 1/(k+1) + 1/(k(k+1)); 3/(3k+1) = 1/k + 1/(-k(3k+1)); 3/(3k+2) = 1/(k+1) + 1/((k+1)(3k+2)); Similarly 4/n+1/x+1/y+1/z is easily solved if you allow one or more of x,y,z to be negative. So, the usual question is whether all n>4 have a solution with x,y,z>0 (and of course all integers). > 2) Can 4/n be represented by fewer than 4 Egyptian Fractions? If it can be represented with one or two, it can be represented with three: 1/x = 1/3x + 1/3x + 1/3x; 1/x + 1/y = 1/x + 1/2y + 1/2y. So this doesn't change the problem. Also, "Egyptian fractions" usually implies that the fractions are distinct, but if 4/n=1/x+1/y+1/z with some of x,y,z equal to each other then one can find another solution where they are all distinct. Proving this is slightly less trivial; I think it was first done by Takenouchi in 1921. See my paper "Ten algorithms for Egyptian fractions" for the full reference and another (maybe the same) proof: http://www.ics.uci.edu/~eppstein/numth/egypt/ -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: 4/N=(1/x)+(1/y)+(1/z): Solution Progress Date: 25 Jun 1999 11:15:00 -0700 Newsgroups: sci.math mathedman@hotmail.com writes: > PROGRESS: I haven't researched the literature on this problem and > am not a number theorist. However, during the past week I've been > able to make significant progress toward proving this conjecture > true (or greatly reducing the candidates for counterexamples). I > realize that much of this may already be known. ... > So what remains unsolved is the class of integers N of the form > N=24m+1 (m>0) [or, N=24k-23 for k>1] This (plus solutions for all N that are non-quadratic-residues mod 5 or 7) is all in Mordell's 1969 number theory textbook. It is not hard to come up with solutions that work for certain residue classes; I've included a few below. It is unlikely that such solutions will exhaust all the possibilities for n (since they generally don't work for quadratic residues modulo whatever, so they won't rule out most squares), but there is at least a chance that they will exhaust all the primes, which would be good enough. One class of solutions arises when there exist a, b such that an+b has a factor f=-1 mod 4ab. (f is not required to be prime.) Equivalently, there exist b and g such that b+g = 0 (mod m), where m = (-n mod 4bg). Why? Suppose we are given a, b, and f as above. Let c=(f+1)/4ab and g=(an+b)/f. Then 4/n = 1/abcn + 1/bcg + 1/acgn. Note that this only finds solutions where two of x, y, z are multiples of n. Sometimes even for prime n, only one multiple of n occurs; e.g. 4/12289 = 1/3078 + 1/1644678 + 1/30317171913. Here are some choices of a, b, and f that work for various modular relations: n=2mod4: a=1, b=1, f=n+1 n=3mod4: a=2, b=1, f=2n+1 n=5mod8: a=1, b=2, f=n+2 n=5mod8: a=1, b=1, f=(n+1)/2 n=8mod12: a=1 b=3 f=n+3 n=12mod16: a=1, b=2, f=(n+2)/2 n=2mod3: a=1, b=1, f=3 n=2mod5 & 1mod3 => 7mod15: a=2, b=1, f=15 n=2mod5 & 1mod4 => 17mod20: a=2, b=5, f=2n+5 n=3mod5 & 1mod3 => 13mod15: a=1, b=2, f=15 n=3mod7: a=2, b=1, f=7 n=5mod7: a=1, b=2, f=7 n=6mod7: a=1, b=1, f=7 n=7mod11: a=3, b=1, f=11 n=8mod11: a=1, b=3, f=11 n=10mod11: a=1, b=1, f=11 2mod11 & 4mod5 => 24mod55: a=2, b=7, f=55 6mod11 & 4mod5 => 39mod55: a=7, b=2, f=55 n=5mod13 & 1mod3 => 31mod39: a=5, b=1, f=39 n=6mod13 & 1mod3 => 19mod39: a=2, b=1, f=39 n=8mod13 & 1mod3 => 34mod39: a=1, b=5, f=39 n=11mod13 & 1mod3 => 37mod39: a=1, b=2, f=39 n=14mod17 & 1mod4 => 65mod68: a=6 b=17 f=6n+17 n=5mod17 & 2mod7 => 107mod119: a=10 b=1 f=119 n=14mod19: a=1 b=5 f=19 n=15mod19: a=5 b=1 f=19 n=18mod19: a=1 b=1 f=19 n=7mod23: a=3, b=2, f=23 n=10mod23: a=2, b=3, f=23 n=11mod23: a=2, b=1, f=23 n=15mod23: a=3, b=1, f=23 n=17mod23: a=1, b=6, f=23 n=19mod23: a=6, b=1, f=23 n=20mod23: a=1, b=3, f=23 n=21mod23: a=1, b=2, f=23 n=22mod23: a=1, b=1, f=23 n=14mod29 & 1mod3 => 43mod87: a=2 b=1 f=87 n=27mod29 & 1mod3 => 85mod87: a=1 b=2 f=87 n=26mod29 & 1mod4 => 113mod116: a=10 b=29 f=10n+29 n=15mod31: a=2 b=1 f=31 n=23mod31: a=4 b=1 f=31 n=23mod31: a=1 b=8 f=31 n=27mod31: a=1 b=4 f=31 n=27mod31: a=8 b=1 f=31 n=29mod31: a=1 b=2 f=31 n=30mod31: a=1 b=1 f=31 n=38mod41 & 1mod4: a=14 b=41 f=14n+41 n=11mod47: a=4 b=3 f=47 n=15mod47: a=3 b=2 f=47 n=22mod47: a=2 b=3 f=47 n=23mod47: a=2 b=1 f=47 n=30mod47: a=3 b=4 f=47 n=31mod47: a=3 b=1 f=47 n=35mod47: a=1 b=12 f=47; a=4 b=1 f=47 n=39mod47: a=6 b=1 f=47 n=41mod47: a=1 b=6 f=47 n=43mod47: a=1 b=4 f=47; a=12 b=1 f=47 n=44mod47: a=1 b=3 f=47 n=45mod47: a=1 b=2 f=47 n=46mod47: a=1 b=1 f=47 n=23mod71: a=3 b=2 f=71 n=31mod71: a=2 b=9 f=71 n=34mod71: a=2 b=3 f=71 n=35mod71: a=2 b=1 f=71 n=47mod71: a=3 b=1 f=71 n=53mod71: a=1 b=18 f=71 n=55mod71: a=9 b=2 f=71 n=59mod71: a=6 b=1 f=71 n=62mod71: a=1 b=9 f=71 n=63mod71: a=9 b=1 f=71 n=65mod71: a=1 b=6 f=71 n=67mod71: a=18 b=1 f=71 n=68mod71: a=1 b=3 f=71 n=69mod71: a=1 b=2 f=71 n=70mod71: a=1 b=1 f=71 -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: eppstein@ics.uci.edu (David Eppstein) Subject: Re: 4/N=(1/x)+(1/y)+(1/z): Solution Progress Date: 30 Jun 99 00:22:38 GMT Newsgroups: sci.math David M Einstein writes: > This is interesting. With a little algebra we can recast this a saying that > the solution arises whenever n + 4 b^2 c has a factor equivalent to -1 mod 4bc. > It appears that n can never be a square. Why? Because Schinzel proved in 1956 that there can be no family of solutions 4/(s*x+t) = 1/p(x) + 1/q(x) + 1/r(x) where p q and r are polynomials (with positive leading terms) and t is a quadratic residue mod s. (I am not familiar with the proof, I have just seen many references to it.) If you had one solution for n, you could always extend it to a family like the one above, where n=s*x+t. But if n is a square, by definition, all pairs (s,t) for which n=s*x+t give quadratic residues. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/