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 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.

Examples

Basic Examples (2)

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]=

Scope (4)

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]=

Properties and Relations (7)

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 2k+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]:=

$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]:=

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]=

Possible Issues (3)

Fractions at positions 2^a-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]:=

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]=

Neat Examples (2)

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]=

Version History

1.0.0 – 03 January 2023

Related Resources

License Information

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