55 lines
1.2 KiB
Rust
55 lines
1.2 KiB
Rust
// [dependencies]
|
|
// num = "0.3"
|
|
|
|
use num::rational::Rational;
|
|
|
|
fn calkin_wilf_next(term: &Rational) -> Rational {
|
|
Rational::from_integer(1) / (Rational::from_integer(2) * term.floor() + 1 - term)
|
|
}
|
|
|
|
fn continued_fraction(r: &Rational) -> Vec<isize> {
|
|
let mut a = *r.numer();
|
|
let mut b = *r.denom();
|
|
let mut result = Vec::new();
|
|
loop {
|
|
let (q, r) = num::integer::div_rem(a, b);
|
|
result.push(q);
|
|
a = b;
|
|
b = r;
|
|
if a == 1 {
|
|
break;
|
|
}
|
|
}
|
|
let len = result.len();
|
|
if len != 0 && len % 2 == 0 {
|
|
result[len - 1] -= 1;
|
|
result.push(1);
|
|
}
|
|
result
|
|
}
|
|
|
|
fn term_number(r: &Rational) -> usize {
|
|
let mut result: usize = 0;
|
|
let mut d: usize = 1;
|
|
let mut p: usize = 0;
|
|
for n in continued_fraction(r) {
|
|
for _ in 0..n {
|
|
result |= d << p;
|
|
p += 1;
|
|
}
|
|
d ^= 1;
|
|
}
|
|
result
|
|
}
|
|
|
|
fn main() {
|
|
println!("First 20 terms of the Calkin-Wilf sequence are:");
|
|
let mut term = Rational::from_integer(1);
|
|
for i in 1..=20 {
|
|
println!("{:2}: {}", i, term);
|
|
term = calkin_wilf_next(&term);
|
|
}
|
|
let r = Rational::new(83116, 51639);
|
|
println!("{} is the {}th term of the sequence.", r, term_number(&r));
|
|
}
|