23 lines
544 B
Crystal
23 lines
544 B
Crystal
require "big"
|
|
|
|
def farey(n)
|
|
a, b, c, d = 0, 1, 1, n
|
|
fracs = [] of BigRational
|
|
fracs << BigRational.new(0,1)
|
|
while c <= n
|
|
k = (n + b) // d
|
|
a, b, c, d = c, d, k * c - a, k * d - b
|
|
fracs << BigRational.new(a,b)
|
|
end
|
|
fracs.uniq.sort
|
|
end
|
|
|
|
puts "Farey sequence for order 1 through 11 (inclusive):"
|
|
(1..11).each do |n|
|
|
puts "F(#{n}): 0/1 #{farey(n)[1..-2].join(" ")} 1/1"
|
|
end
|
|
|
|
puts "Number of fractions in the Farey sequence:"
|
|
(100..1000).step(100) do |i|
|
|
puts "F(%4d) =%7d" % [i, farey(i).size]
|
|
end
|