Suppose, I have a rational number $r$ with $0<r<1$, for example $$r=\frac{53143}{274851}$$

The goal is to write $r$ as a sum of DISTINCT egyptian fractions (fractions with numerator $1$).

The greedy method (always take the smallest possible denominator) leads to the numbers

$$[6, 38, 2706, 34382456, 4763382302120345, 385726786254606395971426367503080]$$

That means $$r=\frac{1}{6}+\frac{1}{38}+\frac{1}{2706}+\frac{1}{34382456}+\frac{1}{4763382302120345}+\frac{1}{385726786254606395971426367503080}$$

The greedy methods usually leads to very large denominators. I would like to have much smaller denominators. I read somewhere that no efficient algorithm is known to find the optimal representation in the sense, that the largest occuring denominator is as small as possible. But I am looking for a method finding a "good" representation in that sense.

A much better solution in the given example would be :

$$[8, 18, 80, 3792, 30539, 48251620]$$

The maximum entry has only $8$ instead of $33$ digits.

Any ideas ?

  • 1
    $\begingroup$ $$[6, 40, 610, 30539, 335929, 366468, 483120, 488624, 549702, 610780]$$ is an even better representation with $10$ terms, but maximum entry only $6$ digits long $\endgroup$ – Peter Dec 15 '16 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.