Home Explore Help
Register Sign In
trizen
/
sidef-scripts
Watch 1
Star 0
Fork 0
Files Issues 0 Pull Requests 0 Wiki
Branch: master
Branches Tags
sidef-scripts
/
Math
/
farey_sequences.sf

farey_sequences.sf 1.1 KB
Permalink History Raw

1234567891011121314151617181920212223242526272829303132333435363738 
  1. #!/usr/bin/ruby
    2. 

  2. 

  3. # The nth Farey sequence in ascending order.
    4. 

  4. 

  5. # See also:
    6. 

  6. #   https://en.wikipedia.org/wiki/Farey_sequence
    7. 

  7. 

  8. func farey_sequence(n) {
    9. 

  9.     var (a, b, c, d) = (0, 1, 1, n)
    10. 

  10. 

  11.     var seq = [a/b]
    12. 

  12. 

  13.     while (c <= n) {
    14. 

  14.         var k = (n+b)//d
    15. 

  15.         (a, b, c, d) = (c, d, k*c - a, k*d - b)
    16. 

  16.         seq << a/b
    17. 

  17.     }
    18. 

  18. 

  19.     return seq
    20. 

  20. }
    21. 

  21. 

  22. for n in (0..10) {
    23. 

  23.     say farey_sequence(n)
    24. 

  24. }
    25. 

  25. 

  26. __END__
    27. 

  27. [0]
    28. 

  28. [0, 1]
    29. 

  29. [0, 1/2, 1]
    30. 

  30. [0, 1/3, 1/2, 2/3, 1]
    31. 

  31. [0, 1/4, 1/3, 1/2, 2/3, 3/4, 1]
    32. 

  32. [0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1]
    33. 

  33. [0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1]
    34. 

  34. [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]
    35. 

  35. [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]
    36. 

  36. [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]
    37. 

  37. [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]
    38. 

  38.