What is the loop invariant of the following function?
Try finding a loop invariant of the following form:
$$
f(x,y) \leq n &lt; g(x,y).
$$

For example, when $y=0$ you could choose $f(x,y) = x$ and $g(x,y) = x+1$, and in the end you want this invariant to imply $b^y \leq n &lt; b^{y+1}$.

To get some intuition, note that if $n = b^k z + w$, where $0 \leq w &lt; b^k$, then after $k$ iterations, we have $x = z$. This can help you formulate the loop invariant.