The CalkinWilfSequence function computes the nth term in the Calkin-Wilf sequence.

The vertices of the Calkin-Wilf tree are labeled with rational numbers $\frac{a}{b}$. The root vertex is defined to be $\frac{1}{1}$. For any vertex $\frac{a}{b}$, its children are $\frac{a}{a\+b}$ and $\frac{a\+b}{b}$.

The Calkin-Wilf sequence is obtained by breadth-first traversal of the Calkin-Wilf tree, where the lesser child is traversed first.

Every positive rational number occurs exactly once in the Calkin-Wilf tree.

$\mathrm{with}\left(\mathrm{NumberTheory}\right)\:$

$\mathrm{CalkinWilfSequence}\left(1\right)$

$1$

$\mathrm{CalkinWilfSequence}\left(2\right)$

$\frac{1}{2}$

$\mathrm{cw}≔\mathrm{GraphTheory}:-\mathrm{Graph}\left(\left\{\left\{''1/1''\,''1/2''\right\}\,\left\{''1/1''\,''2/1''\right\}\,\left\{''1/2''\,''1/3''\right\}\,\left\{''1/2''\,''3/2''\right\}\,\left\{''2/1''\,''2/3''\right\}\,\left\{''2/1''\,''3/1''\right\}\right\}\right)\:$

$\mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(\mathrm{cw}\,\mathrm{style}=\mathrm{tree}\,\mathrm{root}=''1/1''\right)$

$\mathrm{seq}\left(\mathrm{CalkinWilfSequence}\left(n\right)\,n=1..7\right)$

$1,\frac{1}{2},2,\frac{1}{3},\frac{3}{2},\frac{2}{3},3$

DrawCWTree := proc( n, { graphstyle := tree } )
    local cwseq, cwgraph;
    cwseq := (x -> convert( x, 'string' ))~( [ seq( NumberTheory:-CalkinWilfSequence(i), i = 1 .. n ) ] ):
    cwgraph := GraphTheory:-Graph( { seq( { cwseq[i], cwseq[ floor( (1/2) * i ) ] }, i = 2 .. n ) } ):
    return GraphTheory:-DrawGraph( cwgraph, style = graphstyle );
end proc:

$\mathrm{DrawCWTree}\left(15\right)$

$\mathrm{DrawCWTree}\left(63\,\mathrm{graphstyle}=\mathrm{spring}\right)$

The NumberTheory[CalkinWilfSequence] command was introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.