Egyptian fractions

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Hackfleischkannibale
Posts: 171
Joined: Sun Aug 10, 2008 7:51 pm UTC
Location: not the moon... yet.

Egyptian fractions

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?
Last edited by Hackfleischkannibale on Mon Jul 06, 2009 4:23 pm UTC, edited 1 time in total.
If this sentence makes no sense to you, why don't you just change a pig?

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Egyptian fractions

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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Hackfleischkannibale
Posts: 171
Joined: Sun Aug 10, 2008 7:51 pm UTC
Location: not the moon... yet.

Re: Egyptian fractions

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.
If this sentence makes no sense to you, why don't you just change a pig?

Pietro
Posts: 42
Joined: Mon Jan 21, 2008 2:30 pm UTC
Location: Campinas -- Brazil
Contact:

Re: Egyptian fractions

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).

I always wondered about the meaning of life. So I looked it up in the dictionary under "L" and there it was --- the meaning of life. It was not what I expected. (Dogbert)

Pietro
Posts: 42
Joined: Mon Jan 21, 2008 2:30 pm UTC
Location: Campinas -- Brazil
Contact:

Re: Egyptian fractions

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.
I always wondered about the meaning of life. So I looked it up in the dictionary under "L" and there it was --- the meaning of life. It was not what I expected. (Dogbert)

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Egyptian fractions

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 $\frac1n-\frac1{n+1}=\frac1{n(n+1)} \Longrightarrow n\frac1{n+1}+n\frac1{n(n+1)}=1$So you can add 18 to your list above.

e^iπ+1=0
Much, much better than Gooder
Posts: 2065
Joined: Sun Feb 15, 2009 9:41 am UTC
Location: Lancaster

Re: Egyptian fractions

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?
poxic wrote:You, sir, have heroic hair.
poxic wrote:I note that the hair is not slowing down. It appears to have progressed from heroic to rocking.

(Avatar by Sungura)

NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Egyptian fractions

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

Finite and quite small.

Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

Pietro
Posts: 42
Joined: Mon Jan 21, 2008 2:30 pm UTC
Location: Campinas -- Brazil
Contact:

Re: Egyptian fractions

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! ) 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
$\frac{1}{n} - \frac{1}{n+d} = \frac{d}{n(n+d)}\ \Longrightarrow\ n\frac{1}{n+d} + \frac{1}{1+n/d}= 1$
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.
I always wondered about the meaning of life. So I looked it up in the dictionary under "L" and there it was --- the meaning of life. It was not what I expected. (Dogbert)

PM 2Ring
Posts: 3700
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Egyptian fractions

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.

Pietro
Posts: 42
Joined: Mon Jan 21, 2008 2:30 pm UTC
Location: Campinas -- Brazil
Contact:

Re: Egyptian fractions

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...
I always wondered about the meaning of life. So I looked it up in the dictionary under "L" and there it was --- the meaning of life. It was not what I expected. (Dogbert)

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Egyptian fractions

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.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Pietro
Posts: 42
Joined: Mon Jan 21, 2008 2:30 pm UTC
Location: Campinas -- Brazil
Contact:

Re: Egyptian fractions

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.
I always wondered about the meaning of life. So I looked it up in the dictionary under "L" and there it was --- the meaning of life. It was not what I expected. (Dogbert)

RayVenn
Posts: 4
Joined: Fri Aug 21, 2009 7:00 am UTC

Re: Egyptian fractions

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
Last edited by RayVenn on Fri Aug 21, 2009 9:12 pm UTC, edited 1 time in total.