8
$\begingroup$

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:

enter image description here

  • 0
    The [Stern–Brocot tree](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) produces all the positive rationals with simple ones (in some sense) earlier than more complicated ones.2015-06-20

2 Answers 2

10

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.

  • 0
    Apparently num * den is also a type of "height": http://xenharmonic.wikispaces.com/Benedetti+height2012-07-09
2

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.

  • 0
    This is "The beginning of the triangle giving all positive rationals" [A038566](http://oeis.org/A038566) / [A020653](http://oeis.org/A020653) Diagram including skipped equivalent fractions [here](http://www.homeschoolmath.net/teaching/rational-numbers-countable.php).2012-06-14