Given any interval $I=(a,b) \subset \mathbb R^+$, we may order the rationals in $I$ with a denominator-first lexicographic order, as follows: First, we list, in increasing order of numerator, all $q \in I$ that have a denominator of $1$ when written in lowest terms (if any); then we list all $q \in I$ that have a denominator of $2$ when written in lowest terms (if any); and so forth. For example, the rationals in $(5,6)$ would be enumerated as: $$\frac{11}{2}, \frac{16}{3}, \frac{17}{3}, \frac{21}{4}, \frac{23}{4}, \frac{26}{5}, \frac{27}{5}, \frac{28}{5}, \frac{29}{5}, \frac{31}{6}, \frac{35}{6} \dots$$ This is obviously a well-ordering, and is similar in spirit to the Farey sequences of order $n$, although they are not the same thing. (In particular the order I am considering here is not compatible with the usual order $<$ on $\mathbb Q$.)

It is known, for example, that if $a,b$ are irrational then the "first" rational in $(a,b)$ (in the sense of this order) can be computed by comparing the continued fraction representations of $a$ and $b$.

My questions:

  1. Does this order have a standard name? "Denominator-first lexicographic order" is precise, but clumsy. Something non-descriptive but with a person's name attached to it (in the flavor of "Farey sequence") would be fine.
  2. What else (if anything) is known about this order? For example, is there a way to compute the second (or nth) rational in $(a,b)$ using continued fractions or something else?

If I knew a good answer to the first question, I suspect I could probably make some headway on my own with the second question. (Without a distinguished name, this turns out to be very hard to Google.)

For those who are interested in the background to this question, I am working on a paper about locating the first rational square in an interval $(a,a+1)$ (where "first" is relative to this order). I've found lots of interesting results but have been unsuccessful at finding related prior work to make connections to.

Edited to add: With less than 8 hours to go on the bounty, I thought I might provide some more details about the kind of directions I am interested in. Tad's answer below suggests looking at the "canonical" interval $(0,1)$, but what about intervals of the form $(\sqrt{n},\sqrt{n+1})$? Consider by way of example $(\sqrt{13},\sqrt{14})$. The rationals in this interval are, in this well-ordering, $$\frac{11}3, \frac{26}7, \frac{29}8, \frac{37}{10}, \frac{40}{11}, \frac{41}{11}, \frac{47}{13}, \frac{48}{13},\dots $$

Some things are easy to see: For example, the sequence of denominators $$(d_n): 3, 7, 8, 10, 11, 11, 13, 13, \dots$$ may have both skips and repeats. As noted above, the first term in the sequence (namely $\frac{11}3$) can be computed by comparing the continued fractions for $\sqrt{13}$ and $\sqrt{14}$. Is there an analogous way to compute the second or nth term in the sequence? Are there any other known properties of these sequences?


The "canonical" interval to try is $(0,1)$. Based on that, go to the Online Encyclopedia of Integer Sequences and look up the sequence of numerators (which is the concatenation, for all $k\ge2$, of the $\phi(k)$ integers less than $k$ which are relatively prime to $k$: $1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5,\ldots$) Your sequence appears as sequence A038566; there are a ton of references there.

  • 1
    $\begingroup$ Thank you for the suggestion. Do you have any ideas how to deal with intervals that are not of the form $(n,n+1)$? For example, it isn't clear to me at all how to adapt the "canonical" interval to the case of one of the form $(\sqrt{n},\sqrt{n+1})$. $\endgroup$ – mweiss Jun 7 '15 at 18:05
  • $\begingroup$ The same approach works for any interval $(a,b)$ (list in order of increasing denominators, then increasing numerators). For a given denominator $q$ you need to find the least $p$ such that $p/q> a$, which is $aq+1$ if $a q\in \Bbb Z$ and $\lceil a q\rceil$ otherwise. However, while there's a chance there's a formula for the $n$-th rational in the list when $(a,b)=(0,1)$, there's not much chance when $(a,b)=(e,\pi)$. $\endgroup$ – Tad Jun 7 '15 at 22:13
  • $\begingroup$ Yes, I know that one can list the rationals that way for any interval -- that was in the original question. I am wondering if that ordering has a name, and what (if anything) is known about how that ordering behaves. $\endgroup$ – mweiss Jun 7 '15 at 22:42

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.