0
$\begingroup$

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?

2 Answers 2

2

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.

  • 0
    And to get a wider range, piecewise sub-trees. Easy enough.2012-04-03
0

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".

  • 0
    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.2012-04-04