27 lines
877 B
Scala
27 lines
877 B
Scala
object FareySequence {
|
|
|
|
def fareySequence(n: Int, start: (Int, Int), stop: (Int, Int)): LazyList[(Int, Int)] = {
|
|
val (nominator_l, denominator_l) = start
|
|
val (nominator_r, denominator_r) = stop
|
|
|
|
val mediant = ((nominator_l + nominator_r), (denominator_l + denominator_r))
|
|
|
|
if (mediant._2 <= n) fareySequence(n, start, mediant) ++ mediant #:: fareySequence(n, mediant, stop)
|
|
else LazyList.empty
|
|
}
|
|
|
|
def farey(n: Int, start: (Int, Int) = (0, 1), stop: (Int, Int) = (1, 1)): LazyList[(Int, Int)] = {
|
|
start #:: fareySequence(n, start, stop) ++ stop #:: LazyList.empty[(Int, Int)]
|
|
}
|
|
|
|
def main(args: Array[String]): Unit = {
|
|
for (i <- 1 to 11) {
|
|
println(s"$i: " + farey(i).map(e => s"${e._1}/${e._2}").mkString(", "))
|
|
}
|
|
println
|
|
for (i <- 100 to 1000 by 100) {
|
|
println(s"$i: " + farey(i).length + " elements")
|
|
}
|
|
}
|
|
|
|
}
|