Computing Ancestors of # for Stern-Brocot Tree

Question

Reading about the Stern-Brocot tree, the article gives this example:

using 7/5 as an example, its closest smaller ancestor is 4/3, so its left child is (4 + 7)/(3 + 5) = 11/8, and its closest larger ancestor is 3/2, so its right child is (7 + 3)/(5 + 2) = 10/7.

Getting the left and right children seem clear to me:

• left - mediant of # (7/5) and closest smaller ancestor (4/3)
• right- mediant of # (7/5) and closest larger ancestor (3/2)

But, how can I figure out the closest smaller and larger ancestors of 7/5?

Answer 1

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

Answer 2

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.

Output:

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

From this output we derive the required sequence by hand (oh well, the whole thing could have been done by hand in this simple case, but it's useful to have such a computer program for e.g. approximating irrational numbers).

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

More impressive examples are obtained by calculating for irrational numbers, such as $1/\sqrt{2}$:

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

Giving, after e.g. 45 iterations: $$ \frac{318281039}{225058681} < \sqrt{2} < \frac{768398401}{543339720} $$

Answer 3

"But, how can I figure out the closest smaller and larger ancestors of 7/5?"

Here is a method using a version of the subtractive Euclidean algorithm:

A : 7 (1) - 5 (0) = 7
B : 7 (0) - 5 (1) = -5
C : 7 (1) - 5 (1) = 2 A + B
D : 7 (1) - 5 (2) = -3 B + C Adding smallest positive to 'smallest' (lowest absolute value) negative result
E : 7 (2) - 5 (3) = -1 D + E Repeating above procedure
F : 7 (3) - 5 (4) = 1 C + E
G : 7 (5) - 5 (7) = 0 E + F

At each stage the smallest positive and 'smallest' (i.e. closest-to-zero, smallest absolute value) results are added.

The bracketed coefficients at each stage represent convergent fractions.

The coefficients of the equations with equal and smallest positive and negative results (E and F) represent the Bezout identity and are the 'parents' in the Stern Brocot tree. The result of these equations being |1|, 1 is the greatest common divisor of 7 and 5. So the 'parents' are $\frac{3}{4}$ and $\frac{2}{3}$ . They are the two fractions of which $\frac{5}{7}$ is the mediant.

Disregarding A and B - which are the 'set-up' for the algorithm - the positive and negative results are in a sequence of one positive, two negative, one positive and zero. The interpretation of this 'flipping' is that the continued fraction of $\frac{5}{7}$ is [0; 1, 2, 1, 1] or (which is the same thing) [0; 1, 2, 2].

A longer discussion of this adaptation of the subtractive Euclidean algorithm is here: https://simplyfractions.blogspot.com/p/blog-page_5.html