Egyptian fractions
1
func ef(fr) {
2
var ans = []
3
if (fr >= 1) {
4
return([fr]) if (fr.is_int)
5
var intfr = fr.to_i
6
ans << intfr
7
fr -= intfr
8
}
9
var (x, y) = fr.nude
10
while (x != 1) {
11
ans << fr.inv.ceil.inv
12
fr = ((-y % x) / y*fr.inv.ceil)
13
(x, y) = fr.nude
14
}
15
ans << fr
16
return ans
17
}
18
19
for fr in [43/48, 5/121, 2014/59] {
20
"%s => %s\n".printf(fr.as_rat, ef(fr).map{.as_rat}.join(' + '))
21
}
22
23
var lenmax = (var denommax = [0])
24
for b in (2 .. 99) {
25
for a in (1 .. b-1) {
26
var fr = a/b
27
var e = ef(fr)
28
var (elen, edenom) = (e.length, e[-1].denominator)
29
lenmax = [elen, fr] if (elen > lenmax[0])
30
denommax = [edenom, fr] if (edenom > denommax[0])
31
}
32
}
33
34
"Term max is %s with %i terms\n".printf(lenmax[1].as_rat, lenmax[0])
35
"Denominator max is %s with %i digits\n".printf(denommax[1].as_rat, denommax[0].size)
36
say denommax[0]
Copied!

Output:

1
43/48 => 1/2 + 1/3 + 1/16
2
5/121 => 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
3
2014/59 => 34 + 1/8 + 1/95 + 1/14947 + 1/670223480
4
Term max is 44/53 with 8 terms
5
Denominator max is 8/97 with 150 digits
6
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
Copied!
Last modified 1yr ago
Copy link
Contents
Output: