Talk:Stern–Brocot tree

Anonymous comment from article

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

"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

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)

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 ${\sqrt {2}}$ and if you go RRRLLLLLLLRRRRRRRRRRRRRRRLRRRR… you get $\pi$. The continued fraction for the irrational number tells you which path to take. So the continued fraction for the golden ratio is $[1;1,1,1,1,1\ldots ]$, the continued fraction for ${\sqrt {2}}$ is $[1;2,2,2,2,2,\ldots ]$ and the continued fraction for $\pi$ is $3;7,15,1,292,1,1,1,2,\ldots ]$. 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)

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)

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

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?

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)

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)

Sequence that maps N to Q+

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

${\begin{aligned}S(0)&=0\\S(1)&=1\\S(2n)&=S(n)+1,{\text{ for all }}n>0\\S(2n+1)&={\frac {1}{S(2n)}},{\text{ for all }}n>0.\\\end{aligned}}$

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

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

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)

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)