`x=a/b`between 0 and 1 as a sum of reciprocals, always terminates:

- If
`x=0`, terminate. - Else, let
`n=ceil(1/x)`. - Output 1/n.
- Let
`x=x-1/n`. - Repeat.

When `x=a/b`, we output some n satisfying each of the following:

1/n <= a/b < 1/(n-1) n >= b/a > n-1 an >= b > an-a an-b >= 0 > (an-b) - aAfter subtracting

`1/n`, we're left with

`(an-b)/(bn)`. But we know that

`an-b < a`, so even before cancellation the numerator of our fraction decreases. Cancellation can only lower the numerator further. Hence printing

`a/b`will take at most

`a`reciprocals.