1234567891011121314151617181920212223242526272829303132333435363738 |
- #!/usr/bin/ruby
- # The nth Farey sequence in ascending order.
- # See also:
- # https://en.wikipedia.org/wiki/Farey_sequence
- func farey_sequence(n) {
- var (a, b, c, d) = (0, 1, 1, n)
- var seq = [a/b]
- while (c <= n) {
- var k = (n+b)//d
- (a, b, c, d) = (c, d, k*c - a, k*d - b)
- seq << a/b
- }
- return seq
- }
- for n in (0..10) {
- say farey_sequence(n)
- }
- __END__
- [0]
- [0, 1]
- [0, 1/2, 1]
- [0, 1/3, 1/2, 2/3, 1]
- [0, 1/4, 1/3, 1/2, 2/3, 3/4, 1]
- [0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1]
- [0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1]
- [0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1]
- [0, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1]
- [0, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1]
- [0, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1]
|