# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

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

Contributed by:
Ed Pegg Jr

ResourceFunction["CalkinWilf"][ returns the fraction at integer position | |

ResourceFunction["CalkinWilf"][ returns the integer position of fraction | |

ResourceFunction["CalkinWilf"][ returns the integer position of fraction in the Calkin–Wilf sequence. |

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 *a*_{j} is the numerator of term *a*_{j+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.

Find the position of in the Calkin–Wilf sequence:

In[1]:= |

Out[1]= |

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

In[2]:= |

Out[2]= |

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

In[3]:= |

Out[3]= |

Generate terms of the Farey sequence:

In[4]:= |

Out[4]= |

Show their positions in the Calkin–Wilf sequence:

In[5]:= |

Out[5]= |

Use the positions to generate fractions:

In[6]:= |

Out[6]= |

Show the first 42 terms:

In[7]:= |

Out[7]= |

Get back the positions using explicit numerators and denominators:

In[8]:= |

Out[8]= |

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

In[9]:= |

Out[9]= |

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

In[10]:= |

Out[10]= |

Negative values return negative fractions:

In[11]:= |

Out[11]= |

Negative fractions correspond to negative positions:

In[12]:= |

Out[12]= |

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

In[13]:= |

Out[13]= |

Level 5 of the Calkin–Wilf tree:

In[14]:= |

Out[14]= |

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

In[15]:= |

Out[15]= |

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

In[16]:= |

Out[16]= |

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

In[17]:= |

Out[17]= |

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

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

Create a plot of the first 256 values:

In[20]:= |

Out[20]= |

Create a plot of indices for the Farey sequence fractions:

In[21]:= |

Out[21]= |

Fractions at positions 2^{a}-1 are returned as *a* instead of :

In[22]:= |

Out[22]= |

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

In[23]:= |

Out[23]= |

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

In[24]:= |

Out[24]= |

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

In[25]:= |

Out[25]= |

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

In[26]:= |

Out[26]= |

List the denominators of the Calkin–Wilf sequence:

In[27]:= |

Out[27]= |

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

In[28]:= |

Out[28]= |

This is also known as the Fusc sequence:

In[29]:= |

Out[29]= |

Plot the Fusc sequence:

In[30]:= |

Out[30]= |

- 1.0.0 – 03 January 2023

This work is licensed under a Creative Commons Attribution 4.0 International License