Function Repository Resource:

# CalkinWilfTree

Generate a complete binary tree of positive fractions

Contributed by: Ian Ford (Wolfram Research)
 ResourceFunction["CalkinWilfTree"][n] generates a complete binary tree of the positive fractions in the Calkin-Wilf sequence down to level n.

## Details and Options

The fractions on level d are those for which the total of the terms in its continued fraction representation is d+1.
In ResourceFunction["CalkinWilfTree"][n], n can be any non-negative machine integer.
ResourceFunction["CalkinWilfTree"] takes the same options as Tree.

## Examples

### Basic Examples (1)

Generate a complete binary tree of the positive fractions in the Calkin-Wilf sequence down to level 4:

 In[1]:=
 Out[1]=

### Properties and Relations (4)

A fraction has children and :

 In[2]:=
 Out[2]=
 In[3]:=
 Out[3]=

The fractions on level d are those for which the total of the terms in its continued fraction representation is d+1:

 In[4]:=
 Out[4]=

The numerators of the fractions in a breadth-first traversal give Stern's diatomic series:

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=

The terms of Stern's diatomic series are generated by the fusc function:

 In[7]:=
 Out[7]=

Additionally, the denominators give Stern's diatomic series shifted by one:

 In[8]:=
 Out[8]=
 In[9]:=
 Out[9]=

If , , , are the fractions at level d, then :

 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

Define a function that permutes the positions on level d by reversing the corresponding binary integers with d digits:

 In[13]:=

Permute the fractions on each level of a Calkin-Wilf tree:

 In[14]:=
 In[15]:=
 Out[15]=

The result is a Stern-Brocot tree:

 In[16]:=
 Out[17]=

## Version History

• 1.0.0 – 06 January 2023