Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

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|improve this answer
    
And to get a wider range, piecewise sub-trees. Easy enough. –  Andy Shulman Apr 3 '12 at 15:52
add comment

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

$0/11,11/21,11/10$

$0/11,11/32,11/21,22/31,11/10$

$0/11,11/43,11/32,22/53,11/21,33/52,22/31,33/41/11/10$

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|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
add comment

Your Answer

 
discard

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.