2 ms·
I think the cost of removing them (checking every value to see if it's a multiple of another) is greater than the benefit of removing them. My search terminated
by fredley 14y ago
I think the cost of removing them (checking every value to see if it's a multiple of another) is greater than the benefit of removing them. My search terminated though (with no interesting finds) - my fractional values were getting too small and I got a ZeroDivisionError.
- ColinWright 14y agoYou can easily generate all fractions in lowest terms within a disk by using a recursive Farey sequence generator.
- Jtsummers 14y agoReading 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.