83 lines
2 KiB
Text
83 lines
2 KiB
Text
import ballerina/io;
|
|
|
|
class frac {
|
|
int num;
|
|
int den;
|
|
|
|
function init(int num, int den) {
|
|
self.num = num;
|
|
self.den = den;
|
|
}
|
|
|
|
function toString() returns string {
|
|
return string `${self.num}/${self.den}`;
|
|
}
|
|
};
|
|
|
|
function f(frac l, frac r, int n) {
|
|
frac m = new(l.num + r.num, l.den + r.den);
|
|
if m.den <= n {
|
|
f(l, m, n);
|
|
io:print(`${m} `);
|
|
f(m, r, n);
|
|
}
|
|
}
|
|
|
|
function commatize(int n) returns string {
|
|
string s = n.toString();
|
|
if n < 0 { s = s.substring(1); }
|
|
int le = s.length();
|
|
foreach int i in int:range(le - 3, 0, -3) {
|
|
s = s.substring(0, i) + "," + s.substring(i);
|
|
}
|
|
if n >= 0 { return s; }
|
|
return "-" + s;
|
|
}
|
|
|
|
public function main() {
|
|
// task 1. solution by recursive generation of mediants
|
|
foreach int n in 1...11 {
|
|
frac l = new(0, 1);
|
|
frac r = new(1, 1);
|
|
io:print(`F(${n}): ${l} `);
|
|
f(l, r, n);
|
|
io:println(r);
|
|
}
|
|
io:println();
|
|
|
|
// task 2. direct solution by summing totient function
|
|
// 2.1 generate primes to 1000
|
|
boolean[1001] composite = [];
|
|
foreach int p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] {
|
|
foreach int n in int:range(p * 2, 1001, p) { composite[n] = true; }
|
|
}
|
|
|
|
// 2.2 generate totients to 1000
|
|
int[1001] tot = [];
|
|
foreach int i in 0...1000 { tot[i] = 1; }
|
|
foreach int n in 2...1000 {
|
|
if !composite[n] {
|
|
tot[n] = n - 1;
|
|
foreach int a in int:range(n * 2, 1001, n) {
|
|
int f = n - 1;
|
|
int r = a / n;
|
|
while r % n == 0 {
|
|
f *= n;
|
|
r /= n;
|
|
}
|
|
tot[a] *= f;
|
|
}
|
|
}
|
|
}
|
|
|
|
// sum totients
|
|
int sum = 1;
|
|
foreach int n in 1...1000 {
|
|
sum += tot[n];
|
|
if n % 100 == 0 {
|
|
string s1 = n.toString().padStart(4);
|
|
string s2 = commatize(sum).padStart(7);
|
|
io:println(`F(${s1}): ${s2}`);
|
|
}
|
|
}
|
|
}
|