Egyptian Fractions (Calculations)

[Franklin T. Adams-Watters]

An Egyptian fraction is the representation of a positive rational number a/b as \sum_{i=1}^k 1/c_i, where the c_i are distinct positive integers.  Conventionally, the c_i are presented in increasing order.  There are infinitely many representations as an Egyptian fraction for any positive rational number.

The only way I know of to find the minimum number of terms for a given rational is to use a recursive routine (in pseudo-code):

FindEgypt(rat, target, minDen)
   num = Numerator(rat)
   den = Denominator(rat)

   if num = 1 return <den>
   if target = 1 return Fail

   for testDen = max(minDen, ceiling(den/num)) to floor(den*target/num)
      res = FindEgypt(rat - 1/testDen, target - 1, testDen + 1)
      if res <> Fail return Cat(<testDen>, res)
   end

   return Fail
end

Try this routine with increasing values of target until it does not fail.


To minimize (in whatever sense) the terms c_i for a fraction a/b, you need to first find the largest prime power p^j divisor of b.  Now determine the value of the fraction e = a/(b/p^j) in the integers modulo p.  Find the smallest set of integers d_i whose reciprocals, modulo p, sum to e.  (The sense of "smallest" to be used here depends on the sense of smallest you are trying to solve for.)  Now take the values d_i*p^j as some of the terms of the Egyptian fraction.  Calculate the remainder a/b - \sum 1/(d_i*p^j); this will be a fraction whose largest prime power denominator is less than p^j, so you can recursively solve the problem for it.

There are two complications that can arise here.  First, if a is small, the remainder may be negative.  In this case, keep looking for the next smallest set of d_i.  Second, the solution for the remainder may increase the final result.  To deal with this, set this solution aside, and keep checking until a smaller result is found, or the existence of such a result can be ruled out.

For example, consider 13/17, trying to minimize the sum of the terms.  The largest prime power divisor here is 17^1, so e = 13.  The small reciprocals modulo 17 are <1,9,6,13>.  To get a sum of 13, we check partitions of successive integers into distinct parts, to get the first one that totals 13.
For 1:
 <1> |-> <1>, sum = 1.
For 2:
 <2> |-> <9>, sum = 9.
For 3:
 <3> |-> <6>, sum = 6.
 <1,2> |-> <1,9>, sum = 10.
For 4:
 <4> |-> <13>, sum = 13.
 <1,3> |-> <1,6>, sum = 7.

We thus try d = <68>.  13/17-1/68 = 3/4 = 1/2 + 1/4, so we have a represenation as an Egyptian fraction of:
 2,4,68;
with a sum of 74.
If the cost of 3/4 was more than 17, we would have to keep looking to see if a better solution was available.

-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp