Function Repository Resource:

# SternBrocot

Get the position of a fraction or vice-versa in the Stern–Brocot sequence

Contributed by: Ed Pegg Jr
 ResourceFunction["SternBrocot"][num] returns the fraction at integer position num in the Stern–Brocot sequence. ResourceFunction["SternBrocot"][frac] returns the integer position of the fraction frac in the Stern–Brocot sequence. ResourceFunction["SternBrocot"][numer,denom] returns the integer position of fraction in the Stern–Brocot sequence.

## Details

The breadth-first traversal of the Stern–Brocot tree gives the Stern–Brocot sequence, with initial terms as follows:
In this implementation of ResourceFunction["SternBrocot"], f[0]=0 and f[-n]=-f[n], which may be considered nonstandard.
A bit-reversal permutation of the Stern–Brocot tree gives the Calkin–Wilf tree.
The binary length of the index for fraction equals . This can lead to unexpected results. For example, has index 341, but has index 18014398509481984.

## Examples

### Basic Examples (2)

Find the position of in the Stern–Brocot sequence:

 In[1]:=
 Out[1]=

Find the position of in the Stern–Brocot sequence with explicit numerator and denominator:

 In[2]:=
 Out[2]=

Find the fraction at position 960 in the Stern–Brocot sequence:

 In[3]:=
 Out[3]=

Generate terms of the Farey sequence:

 In[4]:=
 Out[4]=

Show their positions in the Stern–Brocot 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 (6)

Negative values return negative fractions:

 In[11]:=
 Out[11]=

Negative fractions correspond to negative positions:

 In[12]:=
 Out[12]=

Level 5 of the Stern-Brocot tree:

 In[13]:=
 Out[13]=

Find the Total of the terms of the ContinuedFraction for level 5 of the Stern-Brocot tree:

 In[14]:=
 Out[14]=

For terms on the same level in the Stern–Brocot binary tree, =1:

 In[15]:=
 Out[15]=

The maximal numerator for level n of the Stern-Brocot tree is Fibonacci[n+1]:

 In[16]:=
 Out[16]=

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

 In[17]:=
 Out[17]=
 In[18]:=
 Out[18]=

Create a plot of the first 256 values:

 In[19]:=
 Out[19]=

Create a plot of indices for the Farey sequence fractions:

 In[20]:=
 Out[20]=

### Possible Issues (3)

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

 In[21]:=
 Out[21]=

SternBrocot returns a Failure if its input is anything other than an integer:

 In[22]:=
 Out[22]=

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

 In[23]:=
 Out[23]=

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

 In[24]:=
 Out[24]=

### Neat Examples (4)

Find fractions of the order 8 FareySequence missing from the order 5 Stern–Brocot binary tree:

 In[25]:=
 Out[25]=

Show the Stern–Brocot binary tree:

 In[26]:=
 Out[26]=

Put the Stern–Brocot binary tree into a hydraulic press:

 In[27]:=
 Out[28]=

Make the Stern–Brocot binary tree with help from IntegerExponent:

 In[29]:=
 Out[29]=

## Version History

• 1.0.0 – 03 January 2023