Representation with distinct egyptian fractions with "small" denominators

Question

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 ?

Answer 1

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.