Egyptian fraction

An Egyptian fraction expresses a nonnegative rational number as a finite sum of positive unit fractions. A computational representation may permit repeated denominators, while the classical distinct-denominator convention adds a further requirement. The empty sum represents zero. For example, $3/7=1/3+1/11+1/231$; each denominator is a positive integer. A representation that permits repetition also has the simple expansion $n/d={\sum }_{j=1}^{n}1/d$ for nonnegative integers $n$ and positive $d$.

For a positive proper residual fraction $n/d$, with $0<n<d$, choose $q=\lceil d/n\rceil$, append the unit fraction $1/q$, and replace the residual by $(nq-d)/(dq)$ in lowest terms. This is a greedy algorithm: the chosen unit fraction is the largest one not exceeding the residual.

The inequalities $q-1<d/n\le q$ imply $0\le nq-d<n$. Thus the numerator of the reduced residual strictly decreases while positive, proving algorithm termination by a nonnegative-integer loop variant. The loop invariant is that the accumulated sum plus the residual is the original rational number. Since $q\ge 2$ and $n/d<1/(q-1)$, the new residual is less than $1/(q(q-1))\le 1/q$. If it remains positive, its next chosen denominator is therefore strictly greater than $q$; this expansion also satisfies the distinct-denominator convention. The proof does not bound the denominators by the input's fixed-width range. Arbitrary-precision arithmetic, checked conversion, or a different representable expansion can therefore be necessary in code.