Function Repository Resource:

CalkinWilf

Source Notebook

Get the position of a fraction or vice-versa within the Calkin–Wilf sequence

Contributed by: Ed Pegg Jr

ResourceFunction["CalkinWilf"][n]

returns the fraction at integer position n in the Calkin–Wilf sequence.

ResourceFunction["CalkinWilf"][frac]

returns the integer position of fraction frac in the Calkin–Wilf sequence.

ResourceFunction["CalkinWilf"][numer,denom]

returns the integer position of fraction in the Calkin–Wilf sequence.

Details

The Calkin–Wilf binary tree has nodes of type with subnodes and .
The breadth-first traversal of the Calkin–Wilf tree gives the Calkin–Wilf sequence, with initial terms shown in the next cell.
In the positive Calkin–Wilf sequence, the denominator of term aj is the numerator of term aj+1. The series of numerators is known as the Fusc sequence.
In this function implementation, f[0]=0 and f[-n]=-f[n], which may be considered nonstandard.
A bit-reversal permutation of the Calkin–Wilf tree gives the Stern–Brocot tree.
The binary length of the index for fraction equals . This can lead to unexpected results. For example, has index 426, but has index 18014398509481984.
ResourceFunction["CalkinWilf"] threads over lists.

Examples

Basic Examples (2) 

Find the position of in the Calkin–Wilf sequence:

In[1]:=
ResourceFunction["CalkinWilf"][22/7]
Out[1]=

Find the position of in the Calkin–Wilf sequence with explicit numerator and denominator:

In[2]:=
ResourceFunction["CalkinWilf"][22, 7]
Out[2]=

Find the fraction at position 519 in the Calkin–Wilf sequence:

In[3]:=
ResourceFunction["CalkinWilf"][519]
Out[3]=

Generate terms of the Farey sequence:

In[4]:=
FareySequence[8]
Out[4]=

Show their positions in the Calkin–Wilf sequence:

In[5]:=
fp = ResourceFunction["CalkinWilf"][FareySequence[8]]
Out[5]=

Use the positions to generate fractions:

In[6]:=
ResourceFunction["CalkinWilf"] /@ fp
Out[6]=

Scope (4) 

Show the first 42 terms:

In[7]:=
terms = ResourceFunction["CalkinWilf"][Range[42]]
Out[7]=

Get back the positions using explicit numerators and denominators:

In[8]:=
ResourceFunction["CalkinWilf"][Numerator[#], Denominator[#]] & /@ terms
Out[8]=

Get back the positions by forcing a denominator of 1 everywhere:

In[9]:=
ResourceFunction["CalkinWilf"][#, 1] & /@ terms
Out[9]=

A two term form is needed for positions of integers since fractions ,,, are returned as 1, 2, 3, 4:

In[10]:=
ResourceFunction["CalkinWilf"][#] & /@ terms
Out[10]=

Properties and Relations (7) 

Negative values return negative fractions:

In[11]:=
ResourceFunction["CalkinWilf"][Range[-10, 10]]
Out[11]=

Negative fractions correspond to negative positions:

In[12]:=
ResourceFunction["CalkinWilf"][#, 1] & /@ ResourceFunction["CalkinWilf"][Range[-10, 10]]
Out[12]=

Terms and are at positions k and 2k+1:

In[13]:=
{ResourceFunction["CalkinWilf"][#], ResourceFunction["CalkinWilf"][2 # + 1]} & /@ Range[20]
Out[13]=

Level 5 of the Calkin–Wilf tree:

In[14]:=
level5 = ResourceFunction["CalkinWilf"][Range[2^(5 - 1), 2^5 - 1]]
Out[14]=

Find the Total of the terms of the ContinuedFraction for level 5 of the Calkin–Wilf tree:

In[15]:=
Total[ContinuedFraction[#]] & /@ level5
Out[15]=

For terms on the same level in the Calkin–Wilf tree, =1:

In[16]:=
Total[1/(Numerator[#] Denominator[#]) & /@ ResourceFunction["CalkinWilf"][Range[2^5, 2^6 - 1]]]
Out[16]=

The maximal numerator for level n of the Calkin–Wilf tree is Fibonacci[n+1]:

In[17]:=
Table[Max[
  Numerator[
   ResourceFunction["CalkinWilf"][Range[2^(a - 1), 2^a - 1]]]], {a, 1,
   10}]
Out[17]=

An unreduced fraction gives the same value as the reduced fraction:

In[18]:=
ResourceFunction["CalkinWilf"][4, 2]
Out[18]=
In[19]:=
ResourceFunction["CalkinWilf"][2, 1]
Out[19]=

Create a plot of the first 256 values:

In[20]:=
ListPlot[ResourceFunction["CalkinWilf"][Range[2^8]]]
Out[20]=

Create a plot of indices for the Farey sequence fractions:

In[21]:=
ListPlot[ResourceFunction["CalkinWilf"][FareySequence[2^6]]]
Out[21]=

Possible Issues (3) 

Fractions at positions 2a-1 are returned as a instead of :

In[22]:=
Table[ResourceFunction["CalkinWilf"][k], {k, 2^# - 2, 2^#}] & /@ Range[10]
Out[22]=

CalkinWilf returns a Failure if its input is anything other than an rational:

In[23]:=
{ResourceFunction["CalkinWilf"][Pi], ResourceFunction["CalkinWilf"][2.0], ResourceFunction["CalkinWilf"][blah]}
Out[23]=

Fractions leading to an index with more than a million digits will be flagged as out of range:

In[24]:=
ResourceFunction["CalkinWilf"][1/3321931]
Out[24]=

Fractions with a million digit index will be evaluated as expected:

In[25]:=
ResourceFunction["CalkinWilf"][1/3321930] // Short[#, 1/2] &
Out[25]=

Neat Examples (2) 

Show the Calkin–Wilf binary tree with nodes of type and sub-nodes and :

In[26]:=
Graph[EdgeList[CompleteKaryTree[5, 2]] /. Thread[Range[31] -> ResourceFunction["CalkinWilf"][Range[31]]], VertexLabels -> Placed[Automatic, Center], VertexSize -> .75, VertexShapeFunction -> Nothing]
Out[26]=

List the denominators of the Calkin–Wilf sequence:

In[27]:=
Denominator[ResourceFunction["CalkinWilf"][#]] & /@ Range[60]
Out[27]=

Prepend a 1 to get the numerators of the Calkin–Wilf sequence:

In[28]:=
Numerator[ResourceFunction["CalkinWilf"][#]] & /@ Range[60]
Out[28]=

This is also known as the Fusc sequence:

In[29]:=
ResourceFunction["Fusc"] /@ Range[60]
Out[29]=

Plot the Fusc sequence:

In[30]:=
ListPlot[
 Numerator[ResourceFunction["CalkinWilf"][#]] & /@ Range[2^12 - 1], PlotRange -> All, AspectRatio -> 2/7]
Out[30]=

Version History

  • 1.0.0 – 03 January 2023

Related Resources

License Information