Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-programming/4/b/solution

For , is equivalent to . The largest allowed unit fraction therefore has the smallest such integer denominator:
The residual is . From we obtain
Thus 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 already has the empty expansion and requires no division by .

New to topics? Read the docs here!