thnik again!

2 Responses to “Growing tomatoes”

1. Richard Sabey Says:
   January 29th, 2009 at 8:26 pm

   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:
   January 29th, 2009 at 8:32 pm

   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]

Leave a Reply