## Growing tomatoes

- Have you been to Egypt?
- Have I been to the moon? Do I like sardines? Am I going bald?
- What are you rambling about?!
- Of all the questions in the world, you picked the one I don’t know the answer to.
- What do you mean?
- The Egyptians used unit fractions. The number one was always in their numerator.
- And?
- I met an Egyptian once and he asked me a question about Egyptian fractions.
- And?
- I don’t know if I was just dreaming or if I met him in Cairo. That is why I can’t answer your question.
- I see. No offence meant.
- No taken.
- What did he ask you?
- He was a strange guy. A farmer. Growing tomatoes along the Nile. He had studied in Alexandria. Once he …
- What was his problem?
- He wondered if 4/n could be written as the sum of just three Egyptian fractions. If it was he would grow his tomatoes differently.
- Let me see if I understand you.
- I have given up a long time ago, but be my guest.
- 4/5 = 1/2 + 1/4 + 1/20.
- That was fast!
- I looked at 4/5 as 80/100 and I knew that 80 can be written as the sum of factors of 100, 50 + 25 + 5.
- Ahem!?
- You know what, I think your friend was right. I think I can prove that 4/n can be written as the sum of just three Egyptian fractions!
- I didn’t say he was my friend.
- OK.
- By the way, he believed that there was only one way to do it. 4/5 = 1/2 + 1/4 + 1/20 and there is no other way to write 4/5 as the sum of three Egyptian fractions.
- That sounds very unlikely. I am sure he was wrong.
- Me too, but I can’t find a counter example.
- No problem. Give me a week and I will find one.
- The tomato growers will thank you.

### 2 Responses to “Growing tomatoes”

1. Richard Sabey Says:

The conjecture that 4/n can be expressed as the sum of no more than 3 Egyptian fractions for any integer n>1 is the Erd?s–Straus conjecture.

Note that if it is true for n, it is true for mn:

4 1 1 1
- = – + – + -
n a b c

4 1 1 1
=> — = — + — + — ___ [1]
mn am bm cm

One algorithm which will be of some use is the “greedy” algorithm; to express some number x greater than 0, take as the first term the largest Egyptian that is no greater than x; if this is not exactly x, apply the greedy algorithm to what remains.

If by “just 3″ you mean “exactly 3″, and there is an expression in fewer terms, you can turn one term into two using the formula

1 1 1
- = — + ——
n n+1 n(n+1)

First, consider the case 3/n, which will turn out to be useful later. If n has the form 3k+1, then we have

3 1 2
—- = — + ———– ___ [2]
3k+1 k+1 (k+1)(3k+1)

which is not so useful. However, more useful is

3 1 1
—- = — + ———– ___ [3]
3k+2 k+1 (k+1)(3k+2)

According to what n is, modulo 4, we have 3 easy cases

4 1
– = -
4m m

4 2 1 1
—- = —- = — + ———–
4m+2 2m+1 m+1 (m+1)(2m+1)

4 1 1
—- = — + ———– ___ [4]
4m+3 m+1 (m+1)(4m+3)

and one tricky one

4 1 3
—- = — + -
4m+1 m+1 N

where
N = (4m+1)(m+1)
This last case entails expressing a fraction of the form 3/N as the sum of 2 Egyptian fractions. If m has the form 3k+2, then
n = 4m+1 = 4(3k+2)+1 = 12k+9
so n and N are multiples of 3, so

4 4
- = —-
n 4m+1

1 3
= — + ———–
m+1 (m+1)(4m+1)

1 1
= — + ———– ___ [5]
m+1 (m+1)(4k+3)

Otherwise, N has the form 3k+1. As we have seen from equation [2], this does not enable us to express 3/N as the sum of 2 Egyptian fractions, so this does not show us how to express 4/n as the sum of 3 Egyptian fractions.

If n has the form 4m+1, then, according to m modulo 3, n has the form 12k+1, 12k+5 or 12k+9. Equation [5] deals with the case n = 12k+9.

If n = 12k+5, then, using the greedy algorithm to determine the first term,

4 4
- = —–
n 12k+5

1 3
= —- + ————-
3k+2 (3k+2)(12k+5)

1 1 1
= —- + ———— + ——————
3k+2 (k+1)(12k+5) (k+1)(3k+2)(12k+5)

using equation [3].

If n = 12k+1,

4 4
- = —–
n 12k+1

1 3
= —- + ————-
3k+1 (3k+1)(12k+1)

and the latter term is of the form in equation [2]. Some such 4/n can be expressed as the sum of 3 Egyptian fractions where the greedy algorithm determines the first term, e.g.

4 1 1 1 1 1 1
– = – + — + — = – + — + —
13 4 20 130 4 18 468

4 1 1 1
– = – + — + —-
25 7 60 2100

but not all: it seems that 4/73 can’t. The greedy algorithm works for n=13, 37, 61, 109; in addition expressions for 4/85 and 4/133 may be derived from ones for 4/5 and 4/7 by multiplying each denominator by 17 or 19, respectively; in each case n has the form 24k+13. Indeed, using the greedy algorithm to determine the first term,

4 1 3
—— = —- + ————–
24k+13 6k+4 (6k+4)(24k+13)

where an expression for the latter term as the sum of 2 Egyptian fractions may be obtained from equation [3], substituting (24k+13)(3k+2) for the 3k+2 of equation [3], then doubling the denominators. That method worked thanks to the first term’s denominator being even; although the second term’s denominator has the form 3k+1, a factor of 2 may be taken out from the denominators, creating a second term whose denominator has the form 3k+2, so that equation [3] can be used on it. This leaves only the case n=24k+1:

4 1 3
—– = —- + ————-
24k+1 6k+1 (6k+1)(24k+1)

If here we are not so greedy with our first term, but take the second-smallest possible denominator, then we have:

4 1 7
—– = ——- + ————-
24k+1 2(3k+1) 2(3k+1)(24k+1)

The last term can be expressed as the sum of 2 Egyptian fractions if 5 or 7 divides 3k+1.
If 5 divides 3k+1, we may use the identity

7 1 1
– = – + -
10 2 5

to express the last term as the sum of 2 Egyptian fractions. This is so iff n has the form 120k+73:

4 1 7
——- = ——– + —————–
120k+73 10(3k+2) 10(3k+2)(120k+73)

1 1 1
= ——– + —————- + —————-
10(3k+2) 2(3k+2)(120k+73) 5(3k+2)(120k+73)

If 7 divides 3k+1, then cancelling 7 top and bottom turns the second term into an Egyptian fraction. This is so iff n has the form 168k+49, in which case n=7(24k+7). The factors 7 and 24k+7 can be dealt with using, respectively, equation [1] with m=7, and equation [4] with m=6k+1:

4 4 1 1
——- = ——– = ——- + ————–
168k+49 7(24k+7) 7(3k+1) 7(3k+1)(24k+7)

These last two methods miss those n=24k+1 where neither 5 nor 7 divides 3k+1, namely 4*6=24 residue classes modulo 5*7*24=840.

I see from [Wikipedia] that a further 16 residue classes modulo 840 are solved, leaving only those n which are 1, 121, 169, 289, 361, or 529 modulo 840.

If n=24k+1 has a non-trivial factorisation ab, then we can reduce this to the 4/a or 4/b case using equation [1]. Thus the smallest counterexample n, if there are any, is prime. 1009 is the smallest prime in any of the above residue classes.

References:
[Wikipedia] http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Straus_conjecture

2. Richard Sabey Says:

Oh rats. This WordPress is at once too clever (turning some of my multiple minuses into posh em-dashes) and inconsistent (I thought I’d determined that “pre” tags worked if they were in angle brackets).

Let’s try pre-tags. The following uses pre-tags enclosed in angle brackets

1 1 1
- = — + ——
n n+1 n(n+1)

The following uses brackets:
[pre]
1 1 1
- = — + ——
n n+1 n(n+1)
[/pre]

How to use LaTeX in a comment.