Function Repository Resource:

SternBrocot

Source Notebook

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.

ResourceFunction["SternBrocot"] threads over lists.

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

$Table[Max[ Numerator[ ResourceFunction["SternBrocot"][Range[2^(a - 1), 2^a - 1]]]], {a, 1, 10}]$

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 2^a-1 are returned as a instead of :

In[21]:=

$Table[ResourceFunction["SternBrocot"][k], {k, 2^# - 2, 2^#}] & /@ Range[10]$

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

Graph[EdgeList[CompleteKaryTree[5, 2]] /. Thread[Range[31] -> ResourceFunction["SternBrocot"][Range[31]]], VertexLabels -> Placed[Automatic, Center], VertexSize -> .75, VertexShapeFunction -> Nothing, ImageSize -> 480]

Out[26]=

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

In[27]:=

part = Complement[FareySequence[8], missed];
flatten = Join[part, Drop[Reverse[1/part], 1]];
Style[Row[flatten, " "], 12]

Out[28]=

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

In[29]:=

$Graphics[ MapIndexed[ Style[Text[#1, {#2[[1]], 6 IntegerExponent[#2[[1]], 2]}], 9] &, Sort[ResourceFunction["SternBrocot"][Range[2^6 - 1]]]], ImageSize -> Medium]$

Out[29]=

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