On Mallows’ variation of the Stern–Brocot tree

Mallows (2011) showed that if we, starting with the initial sequence $\langle \frac{0}{1}, \frac{1}{1} \rangle$, successively insert two fractions between two adjacent fractions in a certain way, then every fraction from $\mathbb{Q} \cap (0,1)$ eventually appears. In this article, we first show that Mallows’ variation $\mathrm{MT}_k (k \geq 0)$ of the Stern–Brocot tree can be obtained from the left subtree $\mathrm{SBT}^L$ of the Stern–Brocot tree. We then present algorithms for the following two questions: Where is the $j^\prime \textrm{th}$ element of $\mathrm{MT}_{k^\prime}$ placed in $\mathrm{SBT}^L$? Conversely, where is the $j \textrm{th}$ element of the $k \textrm{th}$ level of $\mathrm{SBT}^L$ placed in Mallows’ variation? We then do similar things for the tree $\mathrm{R}\textrm{-}\mathrm{DT}$ obtained from the Ducci tree by reversing the paths. More precisely, inspired by the way that we obtained Mallows’ variation from the left subtree of the Stern–Brocot tree, we introduce a variation $\mathrm{VT}_k (k \geq 0)$ of the tree $\mathrm{R}\textrm{-}\mathrm{DT}$ and study analogous questions concerning placement between $\mathrm{VT}_k (k \geq 0)$ and the left subtree $\mathrm{R}\textrm{-}\mathrm{DT}^L$ of the tree $\mathrm{R}\textrm{-}\mathrm{DT}$. We also provide an algorithm, which, given a $k \geq 2$, outputs the ordered set $\mathrm{VT}_k$ as a sequence.

Lastly, we explain how Mallows’ variation of the Stern–Brocot tree and our variation of the tree $\mathrm{R}\textrm{DT}$ are related to each other.

Keywords

Mallows’ variation of the Stern–Brocot tree, Stern–Brocot tree, Ducci tree, reversal of the paths, continued fraction

2010 Mathematics Subject Classification

Primary 11B75. Secondary 11A55.

Full Text (PDF format)

Received 17 November 2021

Published 28 December 2022