Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / b

For a positive remaining fraction $n/d$, the condition $1/q\le n/d$ is equivalent to $q\ge d/n$. Since $1/q$ decreases as the positive integer $q$ increases, choose $q=\lceil d/n\rceil$. The zero fraction needs no term. This is the greedy Egyptian fraction expansion.

The remaining fraction isThe defining inequalities $q-1<d/n\le q$ give $0\le nq-d<n$. Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.