Page 1 of 1

Egyptian fractions

Posted: Sun Jul 05, 2009 8:10 pm UTC
by Hackfleischkannibale
I recently stumbled upon egyptian fractions in the wikipedia, and toy around with them since then. So here's a question I asked myself: For what (natural) numbers N can I find numbers [imath]x_1, x_2, ... , x_i[/imath] so that [imath]x_1+x_2+...+x_i=N[/imath], and [imath]\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_i} = 1[/imath]? How do I do so/Is there an algorithm to do so? What if i is fixed?

Re: Egyptian fractions

Posted: Sun Jul 05, 2009 8:15 pm UTC
by skeptical scientist
Um, what are a and b, and how does any of this depend on N? This doesn't seem like a well-formed question...

But if I had to guess what you were asking, I'd suggesting looking at http://mathworld.wolfram.com/EgyptianNumber.html.

P.S. If you have a property of natural numbers, and you think that property might have a name, but you aren't sure what it is, a good thing to do is figure out the first few numbers which have that property, and then look up that sequence in OEIS.

Re: Egyptian fractions

Posted: Mon Jul 06, 2009 4:30 pm UTC
by Hackfleischkannibale
Er yes, thanks, I mutilated my own question by editing it. Now it's correct. Also, thanks for the article, that answered the first question.
My main question is what I should do if I wanted to find the x'es for, say, N=2009.

Re: Egyptian fractions

Posted: Tue Jul 07, 2009 9:48 am UTC
by Pietro
This problem is fascinating! I haven't solved it, but here's some partial progress. We'll say that a natural number N works iff there are natural numbers x1,...,xi such that x1+...+xi=N and 1/x1+...+1/xi=1.

The first obvious thing I noticed was that perfect squares always work. You just take i=N and all xi=N.

Next, I hand-checked that the following numbers do not work: 2,3,5,6,7,8. But, surprise, there are non-squares that work, and the smallest of these is 10 = 4+4+2. Of course, any number of the form (2+4+...+2k-1+2k)+2k=3*2k-2 works, because (1/2+1/4+...+1/2k-1+1/2k)+1/2k=1. The first few are 1,4,10,22,46,94,190. A similar trick will work with 3k-type numbers, etc.

After this I got lazy, and turned instead to closure properties of the set of numbers that work. The following is straightforward:

Lemma 1. Let N1,...,Nk be numbers that work. Then k*(N1+...+Nk) works.

The proof idea is clear when k=2: say M,N both work, and let

x1+...+xi=M, 1/x1+...+1/xi=1
y1+...+yj=N, 1/y1+...+1/yj=1

Add the equations with 1 on the right-hand side and divide both sides by 2 to get

1/2x1+...+1/2xi+1/2y1+...+1/2yj=1.

Thus 2x1+...+2xi+2y1+...+2yj = 2(M+N) works.

With a similarly simple idea, we can prove:

Lemma 2. Let M,N both work. Then M*N works.

Basically you just multiply 1/x1+...+1/xi=1 by 1/y1+...+1/yj=1 and look at what's in the denominators.

Applying lemmas 1 and 2 to the set of squares {1,4,9,16,25,...} and numbers of the form 3*2k-2 (which are known to work), we get a surprisingly dense set of working numbers. Here is a (not at all exhaustive) list I got by fiddling around:

1,4,9,10,16,22,25,26,28,33,34,38,40,42,46,50,52,...

Of course, just because you can't obtain a number N from perfect squares by lemmas 1&2, doesn't mean a priori that N doesn't work. Unfortunately, I don't have a proof or counterexample of this conjecture, mostly due to laziness: it's quite a bit of work to check that a number doesn't work, because it involves slogging through all its partitions (we can dismiss partitions having a 1 summand, but still).

Has anyone else made progress?

Re: Egyptian fractions

Posted: Tue Jul 07, 2009 10:17 am UTC
by Pietro
A small observation I just made, which answers the last question: lemmas 1 & 2 can never be used to show that any prime number works. (Look at the conclusions in them.) Nevertheless, some prime numbers work! The smallest of these is 11:

2 + 3 + 6 = 11
1/2 + 1/3 + 1/6 = 1

The plot thickens...

Here is an updated list of working numbers, using lemmas 1&2 on 11:

1,4,9,10,11,16,22,24,25,26,28,30,33,34
38,40,42,44,46,48,50,52,54,56,58,60,62,63,64,66,68,69,70,72
88,90,94,99,100,190...

Note the extremely high density of working numbers on the middle line. In fact, for all I know, all numbers between 38 and 72 may work; I just haven't been able to prove it from previous knowledge and lemmas 1&2.

Here's a bold conjecture: the set of non-working numbers is finite.

Re: Egyptian fractions

Posted: Tue Jul 07, 2009 2:45 pm UTC
by Buttons
For the same reason you can get 11, you can always get twice a perfect number minus 1. For instance, 28 is perfect, and 2+4+7+14+28=55, and 1/2+1/4+1/7+1/14+1/28=1.

Oh, and you can also get numbers of the form n(n+1)2. This is because [math]\frac1n-\frac1{n+1}=\frac1{n(n+1)} \Longrightarrow n\frac1{n+1}+n\frac1{n(n+1)}=1[/math]So you can add 18 to your list above.

Re: Egyptian fractions

Posted: Wed Jul 08, 2009 2:59 am UTC
by e^iπ+1=0
You can also add any perfect square simply because all of the numbers can be the same. ie, 6+6+6+6+6+6=36 1/6+1/6+1/6+1/6+1/6+1/6=1

So right now the list is at least
1,4,9,10,11,16,18,22,24,25,26,28,30,33,34,36
38,40,42,44,46,48,49,50,52,54,56,58,60,62,63,64,66,68,69,70,72
81,88,90,94,99,100,121,144,169,190...

Although doesn't that link say that every number ≥78 is strictly egyptian, which also mean that they're all egyptian? Or is it just saying that the numbers which are egyptian are strictly egyptian?

Re: Egyptian fractions

Posted: Wed Jul 08, 2009 3:05 am UTC
by NathanielJ
Pietro wrote:Here's a bold conjecture: the set of non-working numbers is finite.


Finite and quite small.

Spoiler:

Re: Egyptian fractions

Posted: Thu Jul 09, 2009 7:55 am UTC
by Pietro
e^iπ+1=0 wrote:You can also add any perfect square simply because all of the numbers can be the same. ie, 6+6+6+6+6+6=36 1/6+1/6+1/6+1/6+1/6+1/6=1


You're quite right, but it was the first thing we noticed on this thread! :o) You're also right regarding your egyptian/strictly egyptian question. Indeed, it seems (non-obvious to me!) that all numbers at least 78 are egyptian.

By the way, forgive me for using such a bland term as "number that works", instead of the much more obvious and memorable "egyptian number"! I'll stick to the latter from now on.

It might be interesting to try and find a proof here of the weaker fact that "every large enough number is egyptian". I personally found this problem fascinating, full of unexpected structure, even if it's not hard to establish. (E.g. lemmas 1 & 2.) One obvious thing to focus on is that, given lemma 2, it suffices to prove that every sufficiently large prime number is egyptian. We have sort of a handle on about half those cases, because all odd primes are either of the form 4k+1 or 4k+3, and the former are always expressible as a sum of two squares (a pretty theorem in itself, admitting many proofs). Now, that's sort of a handle because we already know that all m² are egyptian, and, by lemma 1, numbers of the form 2(m²+n²) are egyptian too.

Another possible approach is through Lagrange's four-square theorem, which states that every positive integer is the sum of four squares (some possibly 0). Since 0 is not egyptian, that gives us:

(i) If x is a square, then x is egyptian;
(ii) If x is the sum of two (non-zero) squares, then 2x is egyptian;
(iii) If x is the sum of three (non-zero) squares, then 3x is egyptian;
(iv) If x is the sum of four (non-zero) squares, then 4x is egyptian.

We might then try to fiddle around to get all of these down to x.

Finally, using an approach analogous to Buttons', we get the following. Let d be a divisor of n. Then
[math]\frac{1}{n} - \frac{1}{n+d} = \frac{d}{n(n+d)}\ \Longrightarrow\ n\frac{1}{n+d} + \frac{1}{1+n/d}= 1[/math]
So that numbers of the type n(n+d) + (1+n/d) = n² + dn + n/d + 1 are egyptian. Plugging a few values I was able to add to our growing list of egyptian numbers, which now is as follows:

1,4,9,10,11,16,18,20,22,24,25,26,27,28,30,33,34,36
38,40,42,44,46,48,49,50,52,54,56,57,58,60,62,63,64,66,68,69,70,72
81,82,88,90,94,99,100,112,121,126,144,153,169,185,190...

It would be nice to fill out the middle line completely, and to connect it to the first line's long dense run starting with 24.

Re: Egyptian fractions

Posted: Thu Jul 09, 2009 2:25 pm UTC
by PM 2Ring
The Crest of the Peacock: Non-European Roots of Mathematics by George Gheverghese Joseph has an excellent section on Egyptian fractions, and their connection to the Egyptian division algorithm. I heartily recommend it to anyone interested in this topic. And the rest of the book is well worth reading, too.

Unfortunately, it's been quite a few years since I read The Crest of the Peacock, so I can't remember many details. (FWIW, I wrote some software (on the Amiga) at the time to find optimal Egyptian fractions). But one thing I do remember is that Egyptian division and fractions are quite practical when it comes to sharing out things like loaves of bread evenly between a group of people. (Egyptian workers got a bread ration as (part) payment for their daily labour). Using Egyptian division in this sort of calculation will (generally) minimize the number of units that have to be subdivided. It's easy for the less mathematically literate to see that the division is fair, and the wastage due to bread crumbs is also minimized.

Re: Egyptian fractions

Posted: Fri Jul 10, 2009 10:53 am UTC
by Pietro
PM 2Ring, it's true, egyptian fractions give rise to some pretty interesting problems, with a decidedly unique taste. Here are a couple:

[Fun exercise.] Let q be a rational number between 0 and 1. We call 1/x + 1/y + ... + 1/w a strict egyptian representation of q if x,y,...,w are distinct positive integers and 1/x + 1/y + ... + 1/w = q. Prove that every rational in (0,1) has a strict egyptian representation. For extra credit, find an upper bound, in terms of q, on the number of summands in the smallest strict egyptian representation of q.

[Open problem, from Erdos and Graham.] Suppose the natural numbers [imath]\mathbb{N}[/imath] are colored by a finite number of different colors. Prove that there is a monochromatic finite set [imath]S\subset\mathbb{N}[/imath] such that [imath]\sum_{n\in S}\frac{1}{n}=1[/imath].

For a little bit of extra progress on the original problem, here's a theorem of Legendre, extending the already mentioned four-square theorem of Lagrange:

Theorem. A positive integer is expressible as the sum of three squares iff it is not of the form [imath]4^k(8m+7)[/imath].

Therefore, numbers of the form 8m+3 are the sum of three squares. Furthermore, since they are congruent to 3 mod 4, they are not the sum of only two squares. Thus, they must be the sum of three non-zero squares. It follows form lemma 1 that 3*(8m+3) = 24m+9 is always egyptian. In fact, it may be worthwhile to explore things mod 24, since all integers at least 24 are egyptian, and 23 is not.

Updated egyptian list:

1,4,9,10,11,16,18,20,22,24,25,26,27,28,30,33,34,36
38,40,42,44,46,48,49,50,52,54,55,56,57,58,60,62,63,64,66,68,69,70,72
81,82,88,90,94,99,100,105,112,121,126,129,144,153,169,177,185,190...

Re: Egyptian fractions

Posted: Fri Jul 10, 2009 11:48 am UTC
by Token
Pietro wrote:[Open problem, from Erdos and Graham.] Suppose the natural numbers [imath]\mathbb{N}[/imath] are colored by a finite number of different colors. Prove that there is a monochromatic finite set [imath]S\subset\mathbb{N}[/imath] such that [imath]\sum_{n\in S}\frac{1}{n}=1[/imath].

Open? It was proved in 2003 - http://arxiv.org/PS_cache/math/pdf/0311/0311421v1.pdf.

Re: Egyptian fractions

Posted: Sat Jul 11, 2009 5:03 am UTC
by Pietro
Token wrote:Open? It was proved in 2003 - http://arxiv.org/PS_cache/math/pdf/0311/0311421v1.pdf.


Oh my, so it was. I guess I should have read the Wikipedia page. It's a rather ingenious argument, by the way. The only non-elementary bit of mathematics that goes into the result seems to be the prime number theorem.

I swear, every time I looked at this problem I thought, "no way is anyone ever going to solve this, it's too hard and not high-profile enough". Most Ramsey-style results can only guarantee the existence of a relatively flexible kind of substructure ("increasing subsequence", "arithmetic progression", "complete subgraph"); but an actual equation, 1/x + 1/y + ... + 1/w = 1, looked way too rigid and algebraic. I guess it's not all that hard, adding fractions up to 1.

Re: Egyptian fractions

Posted: Fri Aug 21, 2009 7:58 am UTC
by RayVenn
I stumbled on this forum as I was googling the Graham proof for strictly Egyptian numbers. I decided to register and add my small thoughts.

17 = 3+4+4+6 (modified from 3+2+6)
29 = 3+4+6+8+8 (modified from above)
31 = 3+4+6+6+12 (modified from 3+2+6 by multiplying with 2 and then adding 3+6 that makes another 1/2)
32 = 2+3+9+18 (again from 3+2+6, but now using this fact for 6: 2n -> 3n+6n)
35 = 2+6+9+9+9 (from 3+2+6, slicing 3 as with 3+3+3)
37 = 2+5+10+10+10 (2/10+1/10+1/10+1/10 is 1/2)
39 = 3+3+6+9+18 (multiplying 3+2+6 with 3 and adding 3+3 that makes 2/3)
41 = 2+6+6+9+18 (multiplying 3+2+6 with 3 and adding 2+6 that makes 2/3)
43 = 3+6+6+8+8+12 (multiplying 3+4+4+6 with 2 and adding 3+6)
45 = 3+6+6+6+12+12 (3+3+3 to 3+6+6+6+6, then this)
47 = 4+5+6+6+6+20 (2+6+6+6 to 4+4+6+6+6, then 4 -> 5+20)
51 = 4+4+5+6+12+20 (4+4+4+4 to 4+4+4+6+12, then 4 -> 5+20)
53 = 3+4+6+8+16+16 (multiplying 2+4+8+8 with 2 and adding 3+6)

Now we can prove the rest. You already saw that we can multiply an earlier number with 2 and add 3+6. Same can be done with 4+4.
We have shown numbers 24-55 to be Egyptian. 2*24+8 = 56 and 2*24+9 = 57.
2*25+8 = 58 and 2*25+9 = 59. We have "the ball rolling" - all the subsequent whole numbers can be formed from the established ones.

And then to Hackfleischkannibale's original example - how to construct the fractions for 2009:

a) 2009 = 2(1000)+9
b) 1000 = 2(250+250)
c) 250 = 2(121)+8
121 is already a square, but I continue, to get fewer terms.
d) 121 = 2(56)+9
e) 56 = 2(27)+2
f) 27 = 2(9)+9

Now we are in a basic case 9 = 3+3+3 and we can build upwards:
f) 6+6+6+(3+6)
e) 12+12+12+12+6+(2)
d) 24+24+24+24+12+4+(3+6)
c) 48+48+48+48+24+12+8+6+(4+4)
b) (96+96+96+96+48+24+16+12+8+8)+(96+96+96+96+48+24+16+12+8+8)
a) 192+192+192+192+192+192+192+192+96+96
+48+48+32+32+24+24+16+16+16+16+(3+6)

Of course there are solutions with fewer terms, but this way we can always proceed reasonably fast.

EDITED - belatedly noticed the double post rule and merged 2 posts