Calkin-Wilf sequence: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 2,148: | Line 2,148: | ||
83116/51639 is at index: 123456789 |
83116/51639 is at index: 123456789 |
||
</pre> |
|||
=={{header|Vlang}}== |
|||
{{trans|Go}}s. |
|||
<lang vlang>import math.fractions |
|||
import math |
|||
import strconv |
|||
fn calkin_wilf(n int) []fractions.Fraction { |
|||
mut cw := []fractions.Fraction{len: n+1} |
|||
cw[0] = fractions.fraction(1, 1) |
|||
one := fractions.fraction(1, 1) |
|||
two := fractions.fraction(2, 1) |
|||
for i in 1..n { |
|||
mut t := cw[i-1] |
|||
mut f := t.f64() |
|||
f = math.floor(f) |
|||
t = fractions.approximate(f) |
|||
t*=two |
|||
t-= cw[i-1] |
|||
t+=one |
|||
t=t.reciprocal() |
|||
cw[i] = t |
|||
} |
|||
return cw |
|||
} |
|||
fn to_continued(r fractions.Fraction) []int { |
|||
idx := r.str().index('/') or {0} |
|||
mut a := r.str()[..idx].i64() |
|||
mut b := r.str()[idx+1..].i64() |
|||
mut res := []int{} |
|||
for { |
|||
res << int(a/b) |
|||
t := a % b |
|||
a, b = b, t |
|||
if a == 1 { |
|||
break |
|||
} |
|||
} |
|||
le := res.len |
|||
if le%2 == 0 { // ensure always odd |
|||
res[le-1]-- |
|||
res << 1 |
|||
} |
|||
return res |
|||
} |
|||
fn get_term_number(cf []int) ?int { |
|||
mut b := "" |
|||
mut d := "1" |
|||
for n in cf { |
|||
b = d.repeat(n)+b |
|||
if d == "1" { |
|||
d = "0" |
|||
} else { |
|||
d = "1" |
|||
} |
|||
} |
|||
i := strconv.parse_int(b, 2, 64)? |
|||
return int(i) |
|||
} |
|||
fn commatize(n int) string { |
|||
mut s := "$n" |
|||
if n < 0 { |
|||
s = s[1..] |
|||
} |
|||
le := s.len |
|||
for i := le - 3; i >= 1; i -= 3 { |
|||
s = s[0..i] + "," + s[i..] |
|||
} |
|||
if n >= 0 { |
|||
return s |
|||
} |
|||
return "-" + s |
|||
} |
|||
fn main() { |
|||
cw := calkin_wilf(20) |
|||
println("The first 20 terms of the Calkin-Wilf sequnence are:") |
|||
for i := 1; i <= 20; i++ { |
|||
println("${i:2}: ${cw[i-1]}") |
|||
} |
|||
println('') |
|||
r := fractions.fraction(83116, 51639) |
|||
cf := to_continued(r) |
|||
tn := get_term_number(cf) or {0} |
|||
println("$r is the ${commatize(tn)}th term of the sequence.") |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
The first 20 terms of the Calkin-Wilf sequnence are: |
|||
1: 1/1 |
|||
2: 1/2 |
|||
3: 2/1 |
|||
4: 1/3 |
|||
5: 3/2 |
|||
6: 2/3 |
|||
7: 3/1 |
|||
8: 1/4 |
|||
9: 4/3 |
|||
10: 3/5 |
|||
11: 5/2 |
|||
12: 2/5 |
|||
13: 5/3 |
|||
14: 3/4 |
|||
15: 4/1 |
|||
16: 1/5 |
|||
17: 5/4 |
|||
18: 4/7 |
|||
19: 7/3 |
|||
20: 3/8 |
|||
83116/51639 is the 123,456,789th term of the sequence. |
|||
</pre> |
</pre> |
||