*** Welcome to piglix ***

Stern–Brocot tree


In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.

The Stern–Brocot tree was discovered independently by Moritz Stern (1858) and Achille Brocot (1861). Stern was a German number theorist; Brocot was a French clockmaker who used the Stern–Brocot tree to design systems of gears with a gear ratio close to some desired value by finding a ratio of smooth numbers near that value.

The root of the Stern–Brocot tree corresponds to the number 1. The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of continued fractions or mediants, and a path in the tree from the root to any other number q provides a sequence of approximations to q with smaller denominators than q. Because the tree contains each positive rational number exactly once, a breadth first search of the tree provides a method of listing all positive rationals that is closely related to Farey sequences.

Every positive rational number q may be expressed as a continued fraction of the form

where k and a0 are non-negative integers, and each subsequent coefficient ai is a positive integer. This representation is not unique because one has


...
Wikipedia

...