Iterating over members of Stern-Brocot trees

Apr 18, 06:57 AM

Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first n rows of a Stern-Brocot tree.

It’s surprisingly simple. To generate the first n+1 rows, take the values

d8dd58c3ead2c31031724395b0e15d294759e777

where

5d856de78a34b77a3037d9971f7a93a1189dd7ac

given

76ecd9dbf7cfb3668daad2a8873e829b751fe5c5

where

d47008b4c68515aa8c9ad235d95af457b91db777

for odd j and non-negative vi.

Put informally, vi is the number of trailing zeroes in the binary representation of i.

What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.

---

Comment

Commenting is closed for this article.

---