4 ms·
Fractions in the Farey Sequences and the Stern-Brocot Tree
- user51442 9y agoDon't forget the Calkin-Wilf tree: http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwice.pdf http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwic...
- mtzet 9y agoNot a very pretty website, but certainly a pretty subject! This really is the best way of explaining where continued fractions come from. The fact that convergents of the continued fraction provide the best rational approximation always seemed mysterious to me in the classical exposition, but it is almost obvious when explained through the Stern-Brocot tree.
- jstanley 9y agoI don't know about it not being pretty... I thought the website presented the content in a clear and easy-to-follow way. And it loaded quickly, I didn't even need to wait for my browser to download the font before I could see the text. I wish more websites looked like this, instead of plastered with confusing navigation, adverts, popups asking for your email address, "elsewhere on the web", "like, share and subscribe", etc. This is refreshing in its simplicity.
- theoh 9y agoYes, but this kind of HTML authoring is often accompanied by a puritanical dedication to "structural markup". It is often evidence of quite an opinionated, reductive, approach to the web, for better or worse.
- baking 9y agoThe website is actually a pretty exhaustive resource on continued fractions, although I'll admit it's been 40 years since I read Khinchin and I can't honestly say which is more exhaustive.
- btilly 9y agoUseless trivia. You know the 20 questions game? You can actually find any rational through a binary higher/lower search of the Stern-Brocot tree. Finding n/m this way takes O(log(max(|n|, |m|))). The logic is slightly tricky. Some day I'll get bored enough to code it up...
- mathgenius 9y agoThe fractions in the Stern-Brocot tree approximate any real number. There's a statement about this that is equivalent to the Riemann hypothesis.
- mathgenius 9y agoWorking out the Stern-Brocot tree using modular arithmetic leads to some finite shapes because after a while the calculation repeats itself. For example, using mod 5 you get a dodecahedron! These things are called modular curves (iirc.) It's a little bit tricky to figure this out, one hint is that every fraction has two names a/b and -a/-b. In modular arithmetic this is important, eg. 2/3 == -2/-3 == 3/2. So every node of the tree has two labels. (Warning: I may not be explaining this very well.) Once you get to mod 7 you get a three-holed donut shape, called the Klein quartic.
- uryga 9y agoCould someone better versed in math explain why this is important/useful? I skimmed the article, and while I find Ford circles and the trees/tables presented intriguing, I don't really know what to do with the information presented. Do these techniques have any uses / reveal anything interesting?
- baking 9y agoBecause the real numbers are a fiction and fractions are all there is. Google "wilberger."
- mathgenius 9y agoBut fractions are also fiction: who says that one can be divided into two? That's just waiting around for inflation to kick in. And negative numbers: same. It's just hoping for a bigger number to subtract off from. Only the natural numbers exist. All the rest is fantasy.
- baking 9y agoWell, you can describe a negative number or a rational number, but an infinite sequence of non-repeating decimals is a different matter.
- uryga 9y agoWhy?
- baking 9y agoBecause an infinite series of non-repeating decimals . . . can . . . never . . . stop . . .
- uryga 9y agoThat's what I can't understand... For example, I can easily write a program that produces some digits one by one, indefinitely (excluding mechanical failures etc). I won't ever see the whole sequence – as it never ends – but to my mind, it seems like the program describes it. (I think that's basically the computable reals?)
- gabcoh 9y agoI Remember that some Project Euler question requires you to generate this series. I guess I now know how to solve it!