28 lines
551 B
Plaintext
28 lines
551 B
Plaintext
func farey_count(n) { # A005728
|
|
1 + sum(1..n, {|k| euler_phi(k) })
|
|
}
|
|
|
|
func farey(n) {
|
|
|
|
var seq = [0]
|
|
var (a,b,c,d) = (0,1,1,n)
|
|
|
|
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
|
|
}
|
|
|
|
say "Farey sequence for order 1 through 11 (inclusive):"
|
|
for n in (1..11) {
|
|
say("F(%2d): %s" % (n, farey(n).map{.as_frac}.join(" ")))
|
|
}
|
|
|
|
say "\nNumber of fractions in the Farey sequence:"
|
|
for n in (100..1000 -> by(100)) {
|
|
say ("F(%4d) =%7d" % (n, farey_count(n)))
|
|
}
|