Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I only wanted to enumerate the rational numbers between 0 and $a$. Is there a way to "narrow" a Stern-Brocot tree to provide this? I tried keeping my left bound at "$\frac{0}{1}$" and setting my right-bound to "$a$" (where $a$ obviously is a rational) but if I set $a$ to $\frac{11}{10}$, then my first mediant is "1" and my tree is horribly skewed. Setting the left bound to be "$\frac{0}{10}$" alleviates this, but introduces a new problem in that all of my fractions are now non-reduced (modified tree enumerates $\frac{55}{110}$ instead of $\frac{1}{2}$).

Is there a "better" way of doing this?

share|cite|improve this question
up vote 2 down vote accepted

There is just one Stern-Brocot tree, and if you fiddle with the definition you'll get something else, which moreover does not have the properties of the Stern-Brocot tree. The intervals of the rational numbers that have a Stern-Brocot-like tree above them with "all" the properties you want are probably precisely the ones that are beneath a given rational number in the Stern-Brocot tree itself. For instance everything below $\frac7{11}$ is $(\frac58,\frac23)$ so that interval is OK.

share|cite|improve this answer
And to get a wider range, piecewise sub-trees. Easy enough. – Andy Shulman Apr 3 '12 at 15:52

What if you set the left bound to be $0/11$?




Looks like they're all reduced. Of course, this won't enumerate all the rationals, you'll never get any with small denominators. But I don't see how can you have both "complete enumeration" and "all fractions reduced".

share|cite|improve this answer
Normally, it won't enumerate any rational equivalent to one already enumerated. Still, though, that was just an example. In general, how do you do it? – Andy Shulman Apr 3 '12 at 13:18
I'm not sure, because I haven't tried to write out a proof, but if $a$ in lowest terms is $b/c$, and you let your left bound be $0/d$ where $d$ is close to but relatively prime to $d$, you should achieve (rough) balance and have all the fractions be reduced. – Gerry Myerson Apr 4 '12 at 1:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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