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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
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)reply
Appearance of Farey sequences
"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)reply
Golden ratio
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)reply
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)reply
Old comment, but in case someone reads this, there is nothing special about the golden ratio in this regard. There is a one-to-one correspondence between infinite descending paths in the tree and positive irrational numbers. So if you go RLLRRLLRRLL… you get and if you go RRRLLLLLLLRRRRRRRRRRRRRRRLRRRR… you get . The continued fraction for the irrational number tells you which path to take. So the continued fraction for the golden ratio is , the continued fraction for is and the continued fraction for is . The numbers tell you how many right steps to take, then how many left, then how many right, and so on, alternating directions. Rational numbers correspond to paths that terminate—actually pairs of paths, which differ only in their final step, since a rational number has two continued fraction representations.
It's kind of obvious what you have to do, really. If the number at the current vertex is bigger than the number you want, take the left branch; if too small, take the right branch. This will get you arbitrarily close to your number as you descend the tree.
Will Orrick (
talk) 05:00, 25 December 2023 (UTC)reply
Cartesian tree
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)reply
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)reply
Stern's Diatomic Series
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)reply
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?
I agree that not all readers will be comfortable enough with continued fractions to work through the definition. I have added a brief description of what I hope is a more elementary rule for generating the tree.
Will Orrick (
talk) 16:47, 25 December 2023 (UTC)reply
Sequence that maps N to Q+
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)reply
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)reply
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)reply
Easter eggs
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)reply
Merger proposal
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)reply
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)reply
Ok. But both articles would deserve a clarification of their relationship.
D.Lazard (
talk) 18:33, 16 December 2014 (UTC)reply
Practical application to decorative knots
Interestingly
https://www.jcturner.co.nz/the-braider-journal/
in pamphlet 4, Georg Schaake uses this tree to show how to extend regular knots to larger sizes. He does not say if he derived it independently but the notation is remarkably similar if he did. It is a further use of it than mentioned in the article.
MartynShaw (
talk) 00:42, 21 March 2024 (UTC)reply