/* 

  Farey sequence in Picat.

  From http://rosettacode.org/wiki/Farey_sequence
  """
  The Farey sequence (sometimes incorrectly called a Farey series) F[n] 
  of order n is the sequence of completely reduced fractions between 0 and 1 which, when 
  in lowest terms, have denominators less than or equal to n, arranged in order of 
  increasing size. 

  ...

  Task
   - Compute and show the Farey sequence for orders 1 through 11 (inclusive).
   - Compute and display the number of fractions in the Farey sequence for order 
     100 through 1000 (inclusive) by hundreds. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.

% n=5
% {0,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1}

go =>
  member(N,1..11),
  Farey = farey(N),
  println(N=Farey),
  fail,
  nl.

go2 => 
  foreach(N in 100..100..1000)
     F = farey(N),
     println(N=F.length)
  end,
  nl.

% for comparison we ues the float I2/J2 but we then return 
% the "protected" version  ($I2 / J2)
farey(N) = M =>
  M1 = [0=$(0/1)] ++ 
       [I2/J2=$(I2/J2) : I in 1..N, J in I..N, 
        GCD=gcd(I,J),I2 =I//GCD,J2=J//GCD].sort_remove_dups(),
  M = [ E: _=E in M1]. % extract the rational representation