Talk:Stern–Brocot tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field:  Number theory

Anonymous comment from article[edit]

69.137.86.242 (talk · contribs) added the following to the article today, without context or explanation:

According to the referenced article "On the Teeth of Wheels" by Brian Hayes in the Sigma Xi journal American Scientist, the proper first name of Stern was Moritz, not Moriz. Moritz Abraham Stern succeeded Gauss as Ordinary Professor of Mathematics.

I'm moving it here to the talk page, in case someone else wants to follow it up. --Piet Delport 02:38, 21 May 2006 (UTC)

Appearance of Farey sequences[edit]

"an in-order traversal of the first k levels yields the Farey sequence Fk." I don't see that. Looks to me like there is a level which contains 2/5 and 3/5 but not 1/5 or 4/5. Also, for esthetic reasons, I would avoid the barbarous vernacular of the computer programmers: "in-order traversal" :)

No, that statement isn't true. I will try to fix it. Deepmath (talk) 00:10, 9 March 2008 (UTC)

Golden ratio[edit]

It appears to me that, if one descends the tree from 1/1, alternately branching right and left, the resulting sequence of nodes will approach the golden ratio. Can someone prove or disprove this? Vid the Kid (t/c) Yeah, that guy. 05:53, 15 March 2010 (UTC)

Answer to "can someone": yes. Hint: Fibonacci numbers. —David Eppstein (talk) 06:24, 15 March 2010 (UTC)
Yes, that's the approach I had in mind. I just haven't done any formal or rigorous proofs since middle school. Vid the Kid (t/c) Yeah, that guy. 08:04, 15 March 2010 (UTC)

Cartesian tree[edit]

Any citation or simple proof for the statement "it is the unique binary search tree of the rational numbers in which the parent of any vertex q has a smaller denominator than q (or, if q and its parent are both integers, in which the parent is smaller than q)" ? fudo (questions?) 16:16, 4 July 2010 (UTC)

I added a reference for the binary search tree property. As for uniqueness: if one constructs an infinite binary search tree by adding the rational numbers one at a time with this ordering, there is only one place for each new node to go. —David Eppstein (talk) 18:13, 4 July 2010 (UTC)

Stern's Diatomic Series[edit]

Possibly worth mentioning that the numerators going left to right, as well as the denominators going right to left, forms "Stern's Diatomic Series", which can be found at A002487 at OEIS. The construction of the latter sequence is clearly isomorphic with the construction of the SB series, so there's no mystery here except in its bizarre beauty. --Matt Westwood 20:41, 5 September 2011 (UTC)

This sequence is described in more detail in Calkin–Wilf tree. —David Eppstein (talk) 20:58, 5 September 2011 (UTC)

Is this the simplest definition?[edit]

I think in an encyclopedia the intuitive way to arrive at a subject is to be presented always, at least in the introduction. A definition in terms of continues fractions seems to be based on the desire to most easily prove properties of the Stern-Brocot tree, at the expense of understanding. Can someone with more authority than me look into this?

Albert — Preceding unsigned comment added by 80.100.243.19 (talk) 12:42, 23 June 2013 (UTC)

Sequence that maps N to Q+[edit]

A recursive sequence which maps all of the natural numbers (N) to all of the positive rationals (Q+):

Function S maps all of the natural numbers to all of the positive rational numbers. So for every natural number n = 0, 1, 2, ..., S(n) produces a unique rational number p/q in reduced form. The resulting sequence comprises the nodes of the Stern-Brocot tree (but in a slightly different order than a breadth-first traversal of the tree). — Loadmaster (talk) 20:51, 24 October 2013 (UTC)

It's known already — see http://oeis.org/A020650 — but they don't give any references, so it may not be notable enough for an article here. —David Eppstein (talk) 21:20, 24 October 2013 (UTC)
I found this, which uses the Calkin-Wilf tree for mapping the naturals and rationals, but it does not have the same sequence as above. I discovered the sequence S(n) above independently a few years ago and have since seen a few other previously published places where it shows up, including a paper from the 1980s(?) that used this same sequence (a Farey sequence) to prove that the rationals are countable. I can't seem to locate any of them today, though. — Loadmaster (talk) 17:21, 25 October 2013 (UTC)

Easter eggs[edit]

It is not appropriate to use links of this sort:

...in which the vertices correspond [[bijection|precisely]] to...

This breaks the least surprise principle, because a reader who sees a single word in blue is entitled to expect that it goes to an article with that title, a redirect from that title, or a disambiguation of that title.

If there were several words in a row that could be linked to the bijection article, that would be OK probably. However the first sentence is already very heavily linked, probably too heavily. It would be better to find another wording. --Trovatore (talk) 19:36, 11 June 2014 (UTC)

Merger proposal[edit]

I propose to merge Stern–Brocot tree and Calkin–Wilf tree, as they appear to be exactly the same tree. I have no opinion for the name of the merged article. D.Lazard (talk) 18:00, 16 December 2014 (UTC)

They are different trees. E.g. in the Stern–Brocot tree the children of 1/2 are 1/3 and 2/3; in the Calkin–Wilf tree they are instead 1/3 and 3/2. The Stern–Brocot tree is a binary search tree, and is closely related to continued fractions; the Calkin–Wilf tree is instead related to parity of binary coefficients. So I don't think they should be merged. —David Eppstein (talk) 18:17, 16 December 2014 (UTC)
Ok. But both articles would deserve a clarification of their relationship. D.Lazard (talk) 18:33, 16 December 2014 (UTC)