53 lines
1.1 KiB
Text
53 lines
1.1 KiB
Text
import "./math" for Int
|
|
import "./iterate" for Stepped
|
|
import "./fmt" for Fmt
|
|
import "./rat" for Rat
|
|
|
|
var f //recursive
|
|
f = Fn.new { |l, r, n|
|
|
var m = Rat.new(l.num + r.num, l.den + r.den)
|
|
if (m.den <= n) {
|
|
f.call(l, m, n)
|
|
System.write("%(m) ")
|
|
f.call(m, r, n)
|
|
}
|
|
}
|
|
|
|
/* Task 1: solution by recursive generation of mediants. */
|
|
for (n in 1..11) {
|
|
var l = Rat.zero
|
|
var r = Rat.one
|
|
System.write("F(%(n)): %(l) ")
|
|
f.call(l, r, n)
|
|
System.print(r)
|
|
}
|
|
System.print()
|
|
|
|
/* Task 2: direct solution by summing totient function. */
|
|
|
|
// generate primes to 1000
|
|
var comp = Int.primeSieve(1001, false)
|
|
|
|
// generate totients to 1000
|
|
var tot = List.filled(1001, 1)
|
|
for (n in 2..1000) {
|
|
if (!comp[n]) {
|
|
tot[n] = n - 1
|
|
for (a in Stepped.ascend(n*2..1000, n)) {
|
|
var f = n - 1
|
|
var r = (a/n).floor
|
|
while (r%n == 0) {
|
|
f = f * n
|
|
r = (r/n).floor
|
|
}
|
|
tot[a] = tot[a] * f
|
|
}
|
|
}
|
|
}
|
|
|
|
// sum totients
|
|
var sum = 1
|
|
for (n in 1..1000) {
|
|
sum = sum + tot[n]
|
|
if (n%100 == 0) System.print("F(%(Fmt.d(4, n))): %(Fmt.dc(7, sum))")
|
|
}
|