Calkin Wilf Sequence - Maple Help

Home : Support : Online Help : Mathematics : Number Theory : Calkin Wilf Sequence

NumberTheory

 CalkinWilfSequence
 compute the nth term in the Calkin-Wilf sequence

 Calling Sequence CalkinWilfSequence(n)

Parameters

 n - positive integer

Description

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

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{CalkinWilfSequence}\left(1\right)$
 ${1}$ (1)
 > $\mathrm{CalkinWilfSequence}\left(2\right)$
 $\frac{{1}}{{2}}$ (2)

The Calkin-Wilf tree and sequence for the first seven vertices.

 > $\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}$ (3)

Graphs for larger trees can be generated using the following procedure:

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

Compatibility

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