On: The Mystery of 355/113

[ColinWright]

You can easily generate all fractions in lowest terms within a disk by using a recursive Farey sequence generator.

[Jtsummers → ColinWright]

Reading about Farey sequences led me to http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree. This could be used to perform a search of the space of rational numbers with denominator < threshold with each number examined only once.

Edit: Oops, suggested an infinitely long search

[ColinWright → Jtsummers]

The Wilf-Calkin tree also does that:

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

I refer to it as Wilf-Calkin because that's how Neil Calkin refers to it, despite the alphabetical ordering on the Wikipedia page.

Even better, there's an explicit formula for generating rationals, without repeats:

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadt...

[Jtsummers → ColinWright]

Neat, that was in a tab I hadn't reached yet. Though for the purposes of this sort of search, the Stern-Brocot tree has the nice property of being a binary search tree. Allowing you to constrain the breadth as well as the depth of the search.