Fractions in the Farey Sequences and the Stern-Brocot Tree | Hacker News Reader

Fractions in the Farey Sequences and the Stern-Brocot Tree

maths.surrey.ac.uk

50 pointsfanf218 comments

Don't forget the Calkin-Wilf tree: http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwic...

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

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

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

Yes, 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.

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

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

The fractions in the Stern-Brocot tree approximate any real number. There's a statement about this that is equivalent to the Riemann hypothesis.

I Remember that some Project Euler question requires you to generate this series. I guess I now know how to solve it!

Could 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?

Because the real numbers are a fiction and fractions are all there is. Google "wilberger."

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

Well, you can describe a negative number or a rational number, but an infinite sequence of non-repeating decimals is a different matter.

Why?

Because an infinite series of non-repeating decimals . . . can . . . never . . . stop . . .

That'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?)

Sure,there are a large number of "computable reals" such as square roots and taylor series expansions (pi, e, sine, cosine, etc.) which can be estimated to greater and greater precision (always with rational numbers) so we can reasonably talk about them in the abstract (such as use them in equations) much in the same way we talk about the imaginary numbers, quarternions, and octonions. But the idea that you need to construct an entire field of completely undefinable infinite chains of decimals just to allow for a small handful of irrational numbers is kind of absurd.

Norman Wildberger (among others) has put a lot of effort into building up the foundations of mathematics using only the rational numbers and it is quite interesting how far he has gone. He's considered to be a crank by many, but you have to appreciate his effort.

To go back to your original question, his Math Foundations video series, especially #14, #95, and #96 might help.

> Well, you can describe a negative number or a rational number, but an infinite sequence of non-repeating decimals is a different matter.

I'm a bit confused... it sounded like you had objections to defining numbers with infinite decimal expansions, but you're okay with e, pi, etc? Or did you just object to uncomputable reals?

Also I don't know much about this whole topic, but I was taught that you can't fill a continuous line with just the rational numbers – you need the "undefinable" ones for that... What do you think about this?

Also thanks for the references, I might check them out to see what Wildeberger has to say.

Reply on news.ycombinator.com