Computing Ancestors of # for Stern-Brocot Tree

This is not an especially elegant procedure, but it is algorithmic.

Index the levels of the Stern-Brocot tree so that level $n$ has $2^n$ nodes: level $0$ has the root $\frac11$, level $1$ has $\frac12$ and $\frac21$, and so on. Let $T_n$ be the set of rational numbers in $[0,1]$ on level $n$ of the tree, and let $S_n=\bigcup_{k\le n}S_k$; then $S_n\cup\{0\}$ is the Farey sequence of order $F_{n+2}$, where $F_k$ is the $k$-th Fibonacci number. This means that each interior element of $S_n$ is the mediant of its immediate neighbors in $S_n$, so the problem of finding ‘parents’ in the Stern-Brocot tree reduces to finding the neighbors of an interior member of a Farey sequence.

Suppose that $\frac{a}b<\frac{c}d$, and $\frac{a}b$ and $\frac{c}d$ are adjacent in some Farey sequence; it’s well-known that $bc-ad=1$. Thus, if I want to find the left ‘parent’ of $\frac{c}d$ in the Stern-Brocot tree, I need to solve the system

$$\begin{align*} &bc-ad=1\tag{1}\\ &0<b<d\\ &0\le a \end{align*}$$

for $a$ and $b$. Since $c$ and $d$ are relatively prime, the equation $(1)$ has some integer solution $a=a_0,b=b_0$, and the general solution is then

$$\begin{align*} a&=a_0+ck\\ b&=b_0+dk\;, \end{align*}$$

where $k\in\Bbb Z$. Clearly there is at most one $k\in\Bbb Z$ such that $0<b_0+dk<d$, and since $\frac{c}d$ has a left parent, there must be exactly one such $k$. Thus, we may use the extended Euclidean algorithm to compute $a_0$ and $b_0$, set $b=b_0\bmod d$, and use $(1)$ to get $a$. Once we have the left neighbor $\frac{a}b$, we get the right neighbor as $\frac{c-a}{d-b}$.

This takes care of the left half of the Stern-Brocot tree, containing the positive rational numbers not exceeding $1$. The right half is obtained from the left half by reflecting in the vertical centre line and then taking the reciprocal of each rational, so to find the ‘parents’ of a rational greater than $1$ we can find the ‘parents’ of its reciprocal and then take their reciprocals.

A well known property of the Stern-Brocot tree is that there exists a one to one correspondence between the fractions in the interval $[0,1]$ and the fractions in the interval $[1,\infty]$. But it's much simpler to initialize the tree with the interval $[0,1]$. Doing so we get the (Pascal) algorithm below for travelling two paths in the Stern-Brocot tree that lead us to the fraction $5/7$ by enclosing it between a lower bound $m1/n1$ and an upper bound $m2/n2$ with each step. The algorithm halts because it is known that any rational number is in the tree.

program Kevin;

procedure Stern_Brocot(teller,noemer : integer);
{
  Walk through Stern-Brocot tree
  until fraction = teller/noemer
 (English: numerator/denominator)
}
var
  m1,m2,n1,n2 : integer;
begin
{ Initialize tree }
  m1 := 0; n1 := 1;
  m2 := 1; n2 := 0;
  while true do
  begin
  { if teller/noemer < (m1+m2)/(n1+n2) then }
    if (n1+n2)*teller < (m1+m2)*noemer then
  { Tightening }
    begin
    { Upper Bound }
      m2 := m1+m2;
      n2 := n1+n2;
    end else begin
    { Lower Bound }
      m1 := m1+m2;
      n1 := n1+n2;
    end;
    Writeln(m1,'/',n1,' < ',teller,'/',noemer,' < ',m2,'/',n2);
    if (teller/noemer = m1/n1)
    or (teller/noemer = m2/n2) then Break;
  end;
end;

begin
  Stern_Brocot(5,7);
end.

0/1 < 5/7 < 1/1
1/2 < 5/7 < 1/1
2/3 < 5/7 < 1/1
2/3 < 5/7 < 3/4
5/7 < 5/7 < 3/4

1/1 < 7/5 < 1/0
1/1 < 7/5 < 2/1
1/1 < 7/5 < 3/2
4/3 < 7/5 < 3/2
4/3 < 7/5 < 7/5

Note that the closest smaller and larger ancestors are in the tree just before the algorithm halts.

EDIT. My favorite reference is this:

• Stern-Brocot Tree

if (n1+n2)*(n1+n2) < (m1+m2)*(m1+m2)*2 then