/*
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 =>
N = 26,
Farey = farey(N),
println(Farey),
println(len=Farey.length),
nl.
go2 =>
foreach(N in 1..11)
F = farey(N),
println(N=F.length)
end,
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