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/