General error Warning: Cannot modify header information - headers already sent by (output started at /home/bradt/sites/blog.ipsin.org/textpattern/lib/txplib_html.php:1425) on line 4706
General error Warning: Cannot modify header information - headers already sent by (output started at /home/bradt/sites/blog.ipsin.org/textpattern/lib/txplib_html.php:1425) on line 5260
Apr 18, 07: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
where
given
where
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.
Commenting is closed for this article.
« Lindenmayer Systems and the Logo Turtle Swap distances between permutations »
