3
$\begingroup$

The Farey sequence $\mathcal{F}_n$ is the list of all fractions in increasing order (in lowest terms) from $0$ to $1$, having denominator at most $n$. My question is, given some $a/b\in\mathcal{F}_n$ for known $n$, what is the most efficient method to find the fractions in $\mathcal{F}_n$ that are adjacent to $a/b$?

Here is one method. Suppose $\frac{a_0}{b_0}<\frac{a}{b}<\frac{a_1}{b_1}$ are consecutive terms of $\mathcal{F}_n$ for a known $n$. We want to find $a_0/b_0$ and $a_1/b_1$. By definition of $\mathcal{F}_n$, we want to minimize the differences $\frac{a}{b}-\frac{a_0}{b_0}$ and $\frac{a_1}{b_1}-\frac{a}{b}$. There is a well known property of Farey sequences that states if $a/b < a'/b'$ are adjacent terms in $\mathcal{F}_n$, then $\frac{a'}{b'}-\frac{a}{b}=\frac{1}{bb'}$. Then, the differences can be written as $$\frac{a}{b}-\frac{a_0}{b_0}=\frac{ab_0-a_0b}{bb_0}=\frac{1}{bb_0}, \frac{a_1}{b_1}-\frac{a}{b}=\frac{a_1b-ab_1}{b_1b}=\frac{1}{b_1b}.$$ Thus, $ab_0-a_0b=1$ and $a_1b-ab_1=1$. Since $\gcd(a,b)=1$ we can find $(a_0,b_0)$ and $(a_1, b_1)$ due to Bézout's Identity and the extended Euclidean algorithm.

Alternately, we could have drawn a tree diagram of sorts and used bounding arguments to arrive at the solutions.

Are there any other (maybe more efficient?) methods of finding $(a_0, b_0)$ and $(a_1,b_1)$? How can we find the computational complexities of such methods? Is there a method known to be most efficient? Any ideas are appreciated.

$\endgroup$
  • $\begingroup$ The first method that came to my mind is the extended Euclidean algorithm, as you said ... and the Euclidean algorithm is lightning fast in practice. $\endgroup$ – Greg Martin Nov 24 '13 at 8:42
1
$\begingroup$

Here is a slow way of computing the neighbors of $a/b$.

For any $m$ we can ask look at the fractions $0 \leq \frac{1}{m} \leq \frac{2}{m} \leq \dots \leq \frac{m-1}{m} \leq 1$ and ask where $\frac{a}{b}$ fits in here.

We wish to minimize $\frac{a}{b} - \frac{k}{m} = \frac{am-bk}{bm} $ This is just an application of the Euclidean algorithm.

For some $0 \leq r < b$, $am = k b + r $. For a computer k = am/b where we use integer division.


Using the Euclidean algorithm we can speed of the process of long division. We will get some expansion

$ \frac{a}{b} = \cfrac{1}{c_1 + \cfrac{1}{c_2 + \dots } } = [c_1, c_2, \dots ]$

The digits are $b_0=1, b_1 = c_1, b_2 = c_2c_1 + 1, b_3 = c_3b_2 + b_1,\dots $

The algorithmic efficiency of the Euclidean algorithm is discussed on Wikipedia. The number $T(a,b)$ of steps on the Euclidean algorithm for $a/b$ is very chaotic.

For two random $m$-bit numbers $0 < a,b < 2^m$, the number of steps is proportional to $m$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.