5
$\begingroup$

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:

calckin-wilf

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

mod-floor

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – Dylan Cali Jul 20 at 13:33
  • 1
    $\begingroup$ The first term in the denominator is $2a_i/b_i-2(a_i \bmod b_i)/b_i$. $\endgroup$ – marty cohen Jul 20 at 13:54
  • $\begingroup$ got it!!! thank you so much $\endgroup$ – Dylan Cali Jul 20 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.