Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CalkinWilfTree

Source Notebook

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]:=
ResourceFunction["CalkinWilfTree"][4]
Out[1]=

Properties and Relations (4) 

A fraction has children and :

In[2]:=
NestTree[Replace[{a_, b_} :> {{a, a + b}, {a + b, b}}], {1, 1}, 3]
Out[2]=
In[3]:=
% === TreeMap[NumeratorDenominator, ResourceFunction["CalkinWilfTree"][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]:=
TreeMap[Total@*ContinuedFraction, ResourceFunction["CalkinWilfTree"][3]]
Out[4]=

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

In[5]:=
TreeMap[Numerator, ResourceFunction["CalkinWilfTree"][3]]
Out[5]=
In[6]:=
TreeLevel[%, All -> "Data", TreeTraversalOrder -> "BreadthFirst"]
Out[6]=

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

In[7]:=
% === ResourceFunction["Fusc"][Range[15]]
Out[7]=

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

In[8]:=
TreeMap[Denominator, ResourceFunction["CalkinWilfTree"][3]]
Out[8]=
In[9]:=
TreeLevel[%, All -> "Data", TreeTraversalOrder -> "BreadthFirst"]
Out[9]=

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

In[10]:=
ResourceFunction["CalkinWilfTree"][4]
Out[10]=
In[11]:=
TreeLevel[ResourceFunction["CalkinWilfTree"][4], {3} -> "Data"]
Out[11]=
In[12]:=
Total[1/Times @@@ NumeratorDenominator[%]]
Out[12]=

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

In[13]:=
bitreverse[pos_] := IntegerDigits[IntegerReverse[FromDigits[pos - 1, 2], 2, Length[pos]], 2, Length[pos]] + 1

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

In[14]:=
tree = ResourceFunction["CalkinWilfTree"][3];
In[15]:=
TreeMap[First[TreeExtract[tree, {bitreverse[#]}, TreeData]] &, tree, All -> {"Position"}]
Out[15]=

The result is a Stern-Brocot tree:

In[16]:=
ResourceFunction["SternBrocotTree"][3]
Out[17]=

Version History

  • 1.0.0 – 06 January 2023

Source Metadata

Related Resources

License Information