2

I know the Stern-Brocot tree lists out all the possible fractions. But how do I enumerate the fractions that are present in $[a, b]$ where $a$ and $b$ are two fractions.

Sathvik Swaminathan
  • 340
  • 1
    Between any two distinct real numbers, it would be impossible to list out all of the possible fractions due to their density in the real numbers (vaguely, there are infinitely many fractions between any two distinct numbers). Perhaps you can provide more context within your post? – Clayton Mar 29 '18 at 18:41
  • @Clayton They can be enumerated with an infinite list. – Mike Earnest Mar 29 '18 at 18:44
  • Say I want to find all rationals between 1 and 1/2. Is there a particular pattern or design that we have to follow in the tree structure to list them out? I understand that the pattern would be infinitely long. – Sathvik Swaminathan Mar 29 '18 at 18:44
  • Do you mean that you would like a formula that would iterate through all the rationals number in this interval? It is possible because the set of rationals is countable. You could look at proofs of: $\mathbb Q$ is countable – Frostic Mar 29 '18 at 18:45
  • @MikeEarnest: Enumerating the rationals via an infinite sequence seems to be a reasonable question, but trying to "extract all the fractions that are present in $[a,b]$" sounds like he wants a finite list of all the fractions. His comment does indicate otherwise, though. – Clayton Mar 29 '18 at 18:47
  • 1
    Yeah, something like that if it is possible. I was wondering if all rationals in a particular range follow some pattern in the Stern-Brocot tree/series – Sathvik Swaminathan Mar 29 '18 at 18:47
  • @Clayton My apologies, enumeration is what I meant. – Sathvik Swaminathan Mar 29 '18 at 18:48

1 Answers1

3

Repeatedly interleaving mediants (as in the original Stern Brocot tree) should work. See https://arxiv.org/pdf/1301.6807.pdf

ttw
  • 332
  • right, we have just to use $a$ and $b$ as the starting "parents" and then the mediant chain will provide the Stern-Brocot tree in between, i.e. all the rationals in the interval $[a,b]$. – G Cab Nov 23 '18 at 23:50