4
$\begingroup$

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 ?

$\endgroup$
1
  • 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
1
$\begingroup$

Let $r = \frac{a}{N}$ where $a$ and $N$ are positive integers with $1 \le a < N$. Then there is an egyptian fraction decomposition for $r$ where the largest denominator is at most $19N\log(N)(\log(\log(N))^4\log(\log(\log(N)))^2$. For a proof by Yokota, see here. There is also a decomposition such that the largest denominator is at most $4N\log(N)^2\log(\log(N))$ and the number of terms is bounded by $(1 + o(1))\frac{\log(N)}{\log(\log(N))}$. This was proven by Tenenbaum and Yokota, in a paper you can find here.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.