NumberTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Number Theory : NumberTheory/CalkinWilfSequence

NumberTheory

  

CalkinWilfSequence

  

compute the nth term in the Calkin-Wilf sequence

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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 ab. The root vertex is defined to be 11. For any vertex ab, its children are aa+b and a+bb.

• 

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

withNumberTheory:

CalkinWilfSequence1

1

(1)

CalkinWilfSequence2

12

(2)

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

cwGraphTheory:-Graph1/1,1/2,1/1,2/1,1/2,1/3,1/2,3/2,2/1,2/3,2/1,3/1:

GraphTheory:-DrawGraphcw,style=tree,root=1/1

seqCalkinWilfSequencen,n=1..7

1,12,2,13,32,23,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:

Warning, `i` is implicitly declared local to procedure `DrawCWTree`

DrawCWTree15

DrawCWTree63,graphstyle=spring

Compatibility

• 

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

• 

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

See Also

GraphTheory[DrawGraph]

GraphTheory[Graph]

NumberTheory