3 ms·
Reading about Farey sequences led me to http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree. This coul
by Jtsummers 14y ago
Reading about Farey sequences led me to http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree 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
- deleted 14y ago[deleted]
- ColinWright 14y agoThe Wilf-Calkin tree also does that: http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree 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#Breadth_first_traversal http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadt...
- Jtsummers 14y agoNeat, 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.