Is there an upper bound to the amount of distinct fractions in an egyptian fraction?

47 Views Asked by At

We know that any fraction $\dfrac mn$ with $m < n$ can be expressed as a finite number of terms $\dfrac1{x_1} + \dfrac1{x_2} + \cdots + \frac1{x_n}$, using the recursive algorithm $\dfrac mn - \dfrac1q$, also known as an Egyptian Fraction.

However, is the upper bound of the amount of terms infinity? (since each fraction $\dfrac1{x_n}$ can be written as $\dfrac1{q_1} + \dfrac1{q_2} + \cdots + \dfrac1{q_n}$).

Or is there another way to find the upper bound of terms for the recursive algorithm $\dfrac mn - \dfrac1q$?

1

There are 1 best solutions below

0
On

Wikipedia says that the number of terms in $\frac xy$ must sometimes have at least $\log \log y$ terms and gives the examples $1/2, 2/3, 6/7, 42/43, 1806/1807 \ldots.$ This shows the number of terms is unbounded. Any number has a representation with $O(\sqrt {\log y})$ terms