mathr / blog / #

The Farey tree crops up in the Mandelbrot set, a nice introduction can be found in The Mandelbrot Set and The Farey Tree by Robert L. Devaney. The tree operates on rational numbers by Farey addition, and can be defined recursively starting from \(\left(\frac{0}{1},\frac{1}{1}\right)\) with an operation acting on neighbouring numbers:

\[\frac{a}{b} \oplus \frac{c}{d} = \frac{a + c}{b + d}\]

Section 6 of Devaney's paper begins

... Suppose \(0 < \frac{a}{b} < \frac{c}{d} < 1\) are the Farey parents of \(\frac{p}{q}\). ...

In practice it would be nice to be able to compute these Farey parents given \(\frac{p}{q}\). One approach is to perform a search through the tree, starting with bounds at 0 and 1, finding the Farey sum of the bounds and adjusting the bounds at each stage to keep the target fraction within them, stopping when it is reached. Unfortunately this has terrible asymptotic complexity, for example finding the Farey parents of \(\frac{1}{100}\) in this way would step through \(\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots \frac{1}{98}\) before finding the parents \(\left(\frac{0}{1}, \frac{1}{99}\right)\).

Fortunately there is a better way suggested by Siddharth Prasad on math.stackexchange.com: using the extended Euclidean algorithm to solve for \(x\) and \(y\):

\[ q x + p y = \gcd(p, q) = 1 \]

Then one parent is \(-\frac{x}{y}\) and the other can be found by undoing the Farey addition. For example, to find the parents of \(\frac{3}{100}\):

q	r	s	t
	100	1	0
	3	0	1
33	1	1	-33
3	0

which gives one parent \(\frac{1}{33}\), and by Farey addition the other parent is \(\frac{2}{67}\).

The Euclidean algorithm has complexity \(O(\log q)\), which is a vast improvement over the naive search \(O(q)\).