Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 4 / b

For $m>0$, $1/q\le m/n$ is equivalent to $q\ge n/m$. The largest allowed unit fraction therefore has the smallest such integer denominator:The residual is $(mq-n)/(nq)$. From $(q-1)m<n\le qm$ we obtainThus the nonnegative numerator strictly decreases at each nonfinal step, and reduction to lowest terms can only decrease it further. This loop variant proves termination of the greedy Egyptian fraction expansion. The case $m=0$ already has the empty expansion and requires no division by $m$.