Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 11:52, 10 March 2016
, 8 years agoAdded Sidef
m (Added Sidef) |
|||
Line 595:
puts 'Denominator max is %s with %i digits' % [denommax[1], dstr.size], dstr</lang>
{{out}}
<pre>
43/48 => 1/2 + 1/3 + 1/16
5/121 => 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
2014/59 => 34 + 1/8 + 1/95 + 1/14947 + 1/670223480
Term max is 44/53 with 8 terms
Denominator max is 8/97 with 150 digits
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<lang ruby>func ef(fr) {
var ans = []
if (fr >= 1) {
return([fr]) if (fr.is_int)
var intfr = fr.to_i
ans << intfr
fr -= intfr
}
var (x, y) = fr.parts
while (x != 1) {
ans << fr.inv.ceil.inv
fr = ((-y % x) / y*fr.inv.ceil)
(x, y) = fr.parts
}
ans << fr
return ans
}
for fr in [43/48, 5/121, 2014/59] {
"%s => %s\n".printf(fr.as_rat, ef(fr).map{.as_rat}.join(' + '))
}
var lenmax = (var denommax = [0])
for b in range(2, 99) {
for a in range(1, b-1) {
var fr = a/b
var e = ef(fr)
var (elen, edenom) = (e.length, e[-1].denominator)
lenmax = [elen, fr] if (elen > lenmax[0])
denommax = [edenom, fr] if (edenom > denommax[0])
}
}
"Term max is %s with %i terms\n".printf(lenmax[1].as_rat, lenmax[0])
"Denominator max is %s with %i digits\n".printf(denommax[1].as_rat, denommax[0].size)
say denommax[0]</lang>
{{out}}
<pre>
| |||