n-ésimo número racional en la secuencia de Calkin-Wilf

¿Qué es la secuencia de Calkin Wilf?  
Un árbol (o secuencia) de Calkin-Wilf es un árbol binario especial que se obtiene comenzando con la fracción 1/1 y agregando a/(a+b) y (a+b)/b iterativamente debajo de cada fracción a/b. Este árbol genera todos los números racionales. Escribir los términos en una secuencia da 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/ 2, 2/5, 5/3, 3/4, 4/1,… La sucesión tiene la propiedad de que cada denominador es el siguiente numerador.
 

La imagen de arriba es el árbol de Calkin-Wilf donde se enumeran todos los números racionales. Los hijos de un Node a/b se calculan como a/(a+b) y (a+b)/b.
La tarea es encontrar el n-ésimo número racional en la amplitud del primer recorrido de este árbol.  
Ejemplos: 
 

Input : 13
Output : [5, 3]

Input : 5
Output : [3, 2]

Explicación: este árbol es un árbol de búsqueda binaria perfecta y necesitamos pasos de piso (log (n)) para calcular el número racional enésimo. El concepto es similar a buscar en un árbol de búsqueda binario. Dado n, seguimos dividiéndolo por 2 hasta obtener 0. Devolvemos la fracción en cada etapa de la siguiente manera:
 

    if n%2 == 0
        update frac[1]+=frac[0]
    else
        update frac[0]+=frac[1]

A continuación se muestra el programa para encontrar el número n en la secuencia de Calkin Wilf:
 

// C++ program to find the
// nth number in Calkin
// Wilf sequence:
# include<bits/stdc++.h>
using namespace std;
 
int frac[] = {0, 1};
 
// returns 1x2 int array 
// which contains the nth
// rational number
int nthRational(int n)
{
    if (n > 0)
        nthRational(n / 2);
 
    // ~n&1 is equivalent to
    // !n%2?1:0 and n&1 is
    // equivalent to n%2
    frac[~n & 1] += frac[n & 1];
}
 
// Driver Code
int main()
{
    int n = 13; // testing for n=13
     
    // converting array
    // to string format
    nthRational(n);
    cout << "[" << frac[0] << ","
         << frac[1] << "]" << endl;
    return 0;
}
 
// This code is contributed
// by Harshit Saini

// Java program to find the nth number
// in Calkin Wilf sequence:
import java.util.*;
 
public class GFG {
    static int[] frac = { 0, 1 };
 
    public static void main(String args[])
    {
        int n = 13; // testing for n=13
 
        // converting array to string format
        System.out.println(Arrays.toString(nthRational(n)));
    }
 
    // returns 1x2 int array which
    // contains the nth rational number
    static int[] nthRational(int n)
    {
        if (n > 0)
            nthRational(n / 2);
 
        // ~n&1 is equivalent to !n%2?1:0
        // and n&1 is equivalent to n%2
        frac[~n & 1] += frac[n & 1];
         
 
        return frac;
    }
}

# Python program to find
# the nth number in Calkin
# Wilf sequence:
frac = [0, 1]
 
# returns 1x2 int array
# which contains the nth
# rational number
def nthRational(n):
    if n > 0:
        nthRational(int(n / 2))
     
    # ~n&1 is equivalent to
    # !n%2?1:0 and n&1 is
    # equivalent to n%2
    frac[~n & 1] += frac[n & 1]
     
    return frac
 
# Driver code
if __name__ == "__main__":
     
    n = 13 # testing for n=13
     
    # converting array
    # to string format
    print(nthRational(n))
     
# This code is contributed
# by Harshit Saini

// C# program to find the nth number
// in Calkin Wilf sequence:
using System;
 
class GFG
{
    static int[] frac = { 0, 1 };
 
    public static void Main(String []args)
    {
        int n = 13; // testing for n=13
 
        // converting array to string format
        Console.WriteLine("[" + String.Join(",",
                                nthRational(n)) + "]");
    }
 
    // returns 1x2 int array which
    // contains the nth rational number
    static int[] nthRational(int n)
    {
        if (n > 0)
            nthRational(n / 2);
 
        // ~n&1 is equivalent to !n%2?1:0
        // and n&1 is equivalent to n%2
        frac[~n & 1] += frac[n & 1];
         
        return frac;
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to find the nth number
// in Calkin Wilf sequence:
let frac = [0, 1];
 
let n = 13; // testing for n=13
 
// converting array to string format
document.write(`[${nthRational(n)}]`)
 
// returns 1x2 int array which
// contains the nth rational number
function nthRational(n) {
    if (n > 0)
        nthRational(Math.floor(n / 2));
 
    // ~n&1 is equivalent to !n%2?1:0
    // and n&1 is equivalent to n%2
    frac[~n & 1] += frac[n & 1];
    return frac;
}
 
// This code is contributed by _saurabh_jaiswal
 
</script>

[5, 3]

Explicación: 
Para n = 13,