# Is there a sequence that contains every rational number once, but with the “simplest” fractions first?

The Calkin-Wilf sequence contains every positive rational number exactly once:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, ….

I'd consider 5/1 to be a "simpler" ratio than 8/5, but it appears later in the series.

1. Is there a mathematical term for the "simpleness" of a ratio? It might be something like the numerator times the denominator, or maybe there are other ways to measure.

2. Is there a sequence that contains all the positive rational numbers, but with the "simpleness" of the ratios monotonically increasing?

(Small integer ratios are found in Just intonation, polyrhythm, orbital resonance, etc.)

If you use the Calkin-Wilf sequence with the num*den measure, for instance, it looks like this: • I guess you mean a sequence with a nice closed-form expression for its terms? – Cocopuffs Jun 13 '12 at 21:33
• @Cocopufs: As opposed to what? – endolith Jun 13 '12 at 21:36
• @endolith: As opposed to a sequence that doesn't have a nice closed formula, such as (presumably, depending on one's standards for niceness) the one Arturo defines in his answer. – hmakholm left over Monica Jun 13 '12 at 21:40
• You may be interested in the so called "Farey sequences" (see en.wikipedia.org/wiki/Farey_sequence for details). Letting $F_n$ denote the Farey sequence of order $n$, if you restrict your attention to $[0,1]$, you can list all of the rationals in this interval in a way that I think you might like by first listing the elements of $F_1$, then the elements of $F_2$ that aren't in $F_1$, then the elements of $F_3$ that aren't in $F_2$, and so on. Not quite what you are asking about (because of the $[0,1]$ restriction), but very similar. – leslie townes Jun 14 '12 at 1:10
• @leslietownes You can easily extend the Farey sequences to include all rationals. Instead of starting with a right endpoint of $\frac11$, you start with a right endpoint of $\frac10=\infty$, and then do the construction exactly as usual. Then then first Farey seqence $F_1$ is just $\langle \frac11\rangle$, the second is $\langle\frac12,\frac21\rangle$, and so on. Subsequent Farey sequences begin with the usual elements in the first half, and then follow with their reciprocals in the second half. – MJD Aug 2 '12 at 11:59

A common measure of how "complicated" a (reduced) fraction is is the height:

Definition. Let $\frac{r}{s}$ be a rational number, with $\gcd(r,s)=1$. The height of $\frac{r}{s}$ is $\mathrm{ht}\left(\frac{r}{s}\right)=\max\{|r|,|s|\}$.

Among those of the same height, you can order them by comparing the minimum. For those with the same minimum, you can compare values. So one possibility is:

If $\frac{r}{s}$ and $\frac{x}{y}$ are positive rationals with $\gcd(r,s)=\gcd(x,y)=1$, then we say $\frac{r}{s}\preceq \frac{x}{y}$ if and only if

1. $\mathrm{ht}(\frac{r}{s})\lt \mathrm{ht}(\frac{x}{y})$; or
2. $\mathrm{ht}(\frac{r}{s}) = \mathrm{ht}(\frac{x}{y})$ and $\min(r,s)\lt \min(x,y)$; or
3. $\mathrm{ht}(\frac{r}{s})=\mathrm{ht}(\frac{x}{y})$, and $\min(r,s)=\min(x,y)$; and $\frac{r}{s}\leq \frac{x}{y}$.

You would get:

1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, 2/5, 5/2, 3/5, 5/3, 4/5, 5/4, 1/6, 6/1, 5/6, 6/5, ...

Don't know about a closed formula, though.

Note/Clarification: The height is very standard, especially in Diophantine Analysis and Arithmetic Geometry.

I don't know about the rest of the order I present, though it seems like a natural extension (or one could prefer listing larger rationals first in point 3. Inserting the negatives would also allow for several small variations.

You could measure simplicity by the sum of the numerator and denominator (the "length", as it would be known in some parts of Number Theory), breaking ties by, say, size of numerator.

1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1,....

This is essentially the ordering you get out of the usual proof that the (positive) rationals are countable, except that in that proof you include 2/4 and 2/6 and 3/6 and so on. The price of leaving out those duplications is that you can't expect a simple formula for the $n$th rational.

• This is "The beginning of the triangle giving all positive rationals" A038566 / A020653 Diagram including skipped equivalent fractions here. – endolith Jun 14 '12 at 19:28