Generating Calkin-Wilf sequence in Python, but I don't understand the math

Question

This correctly generates the Calkin-Wilf sequence:

def calkin_wilf():
    a, b = 1, 1
    while True:
        yield a, b
        a, b = b, a - 2*(a%b) + b

g = calkin_wilf()
ret = [next(g) for _ in range(5)]
print(ret)

# [(1, 1), (1, 2), (2, 1), (1, 3), (3, 2)]

I understand the Python code itself, but I'm struggling with how they arrived at that math formula for the next denominator in the sequence.

I know that the next numerator of a number in the Calkin-Wilf sequence is the denominator of the previous number. That's easy.

But given a number $\frac{a}{b}$, why does $a- 2 \cdot (a \bmod b) + b$ give the next denominator in the sequence?

The only clues I have is that it is a manipulation of this formula:

and that the modulo operator can somehow be used to calculate the floor of a number:

I've tried to work things out on paper but I can't figure it out. Could someone walk through the math for me?

Sources:

[1] https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

[2] https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Mod_operator

Answer 1

If $q_i =\dfrac{a_i}{b_i} $, then

$\begin{array}\\ q_{i+1} &=\dfrac{1}{2\lfloor q_i \rfloor -q_i+1}\\ &=\dfrac{1}{2\lfloor \dfrac{a_i}{b_i} \rfloor -\dfrac{a_i}{b_i}+1}\\ &=\dfrac{1}{2 \dfrac{a_i-(a_i \bmod b_i)}{b_i} -\dfrac{a_i}{b_i}+1}\\ &=\dfrac{1}{-2\dfrac{a_i \bmod b_i}{b_i} +\dfrac{a_i}{b_i}+1}\\ &=\dfrac{b_i}{-2(a_i \bmod b_i) +a_i+b_i}\\ \end{array} $

so

$a_{i+1} = b_i, b_{i+1} = -2(a_i \bmod b_i) +a_i+b_i $.