50 lines
881 B
Swift
50 lines
881 B
Swift
class Farey {
|
|
let n: Int
|
|
|
|
init(_ x: Int) {
|
|
n = x
|
|
}
|
|
|
|
//using algorithm from wikipedia
|
|
var sequence: [(Int,Int)] {
|
|
var a = 0
|
|
var b = 1
|
|
var c = 1
|
|
var d = n
|
|
var results = [(a, b)]
|
|
while c <= n {
|
|
let k = (n + b) / d
|
|
let oldA = a
|
|
let oldB = b
|
|
a = c
|
|
b = d
|
|
c = k * c - oldA
|
|
d = k * d - oldB
|
|
results += [(a, b)]
|
|
}
|
|
return results
|
|
}
|
|
|
|
var formattedSequence: String {
|
|
var s = "\(n):"
|
|
for pair in sequence {
|
|
s += " \(pair.0)/\(pair.1)"
|
|
}
|
|
return s
|
|
}
|
|
|
|
}
|
|
|
|
print("Sequences\n")
|
|
|
|
for n in 1...11 {
|
|
print(Farey(n).formattedSequence)
|
|
}
|
|
|
|
print("\nSequence Lengths\n")
|
|
|
|
for n in 1...10 {
|
|
let m = n * 100
|
|
print("\(m): \(Farey(m).sequence.count)")
|
|
}
|