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

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 Answer

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$$.

• Could you explain the jump from $\dfrac{1}{2 \dfrac{a_i-(a_i \bmod b_i)}{b_i} -\dfrac{a_i}{b_i}+1}\\$ to $\dfrac{1}{-2\dfrac{a_i \bmod b_i}{b_i} +\dfrac{a_i}{b_i}+1}\\$ for me? I'm just not seeing it. How do you reduce $a_i - (a_i \bmod b_i)$ to just $a_i \bmod b_i$ ? – Dylan Cali Jul 20 at 13:33
• The first term in the denominator is $2a_i/b_i-2(a_i \bmod b_i)/b_i$. – marty cohen Jul 20 at 13:54
• got it!!! thank you so much – Dylan Cali Jul 20 at 14:10