Narrowing a Stern-Brocot tree

245 Views Asked by At

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

There are 2 best solutions below

1
On BEST ANSWER

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.

2
On

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