Unit fraction ($1/n$)

A unit fraction is $1/n$ for a positive integer $n$. Its numerator is one, so it is already a reduced fraction; the denominator determines its value uniquely. For example, $1/2$ and $1/7$ are unit fractions, while $2/7$ is not.

Every unit fraction lies in $(0,1]$, including $1/1=1$. A rational number can have several expressions as a sum of unit fractions: $1/2=1/3+1/6$, for example. An Egyptian fraction requires such a finite representation, usually with distinct denominators.

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.