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
    I guess you mean a sequence with a nice closed-form expression for its terms?2012-06-13
  • 0
    @Cocopufs: As opposed to what?2012-06-13
  • 2
    @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.2012-06-13
  • 0
    It's been nearly 5 years since I was told about this, but this is the first time I've heard of the name. Thanks for posting this!2012-06-13
  • 3
    You may be interested in the so called "Farey sequences" (see http://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.2012-06-14
  • 0
    @Cocopufs: No, it doesn't have to have a closed-form expression, it just has to be possible to generate with a computer program.2012-06-14
  • 0
    @leslietownes: So that would be (1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, 5/8, 7/8, ...)? Well the [1,∞] part is just the inverse of the [0,1] part, right? So every item could have its inverse inserted directly after it?2012-06-14
  • 0
    @endolith yeah, that'd be it (although, maybe begin with $0, 1$). Starting with that list, then inserting inverses after each element of that list would work. I hadn't thought of that, but it's an interesting way to do it.2012-06-14
  • 0
    If you compare using the product of numerator and denominator, you would have, for example, $\frac{1}{31}$ be "simpler" than $\frac{5}{6}$. Is that something you want? Or do you want fractions that involve smaller numbers to be "simpler" than ones that involve larger ones?2012-06-14
  • 0
    @ArturoMagidin: Not sure. In musical harmony, "smaller" integer ratios are considered more consonant, and log(a*b) is one way to measure the "smallness", but there are also others.2012-06-14
  • 1
    @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.2012-08-02
  • 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
    This is apparently the "canonical bijection from positive integers to positive rationals" [A038568](http://oeis.org/A038568) / [A038569](http://oeis.org/A038569)2012-06-14
  • 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