Greedy algorithm for Egyptian fractions: Difference between revisions

</pre>

=={{header|Ruby}}==

{{trans|Python}}

<lang ruby>def ef(fr)

ans = []

if fr >= 1

return [[fr.to_i], Rational(0, 1)] if fr.denominator == 1

intfr = fr.to_i

ans, fr = [intfr], fr - intfr

end

x, y = fr.numerator, fr.denominator

while x != 1

ans << Rational(1, (1/fr).ceil)

fr = Rational(-y % x, y * (1/fr).ceil)

x, y = fr.numerator, fr.denominator

end

ans << fr

end

for fr in [Rational(43, 48), Rational(5, 121), Rational(2014, 59)]

puts '%s => %s' % [fr, ef(fr).join(' + ')]

end

lenmax = denommax = [0]

for b in 2..99

for a in 1...b

fr = Rational(a,b)

e = ef(fr)

elen, edenom = e.length, e[-1].denominator

lenmax = [elen, fr] if elen > lenmax[0]

denommax = [edenom, fr] if edenom > denommax[0]

end

end

puts 'Term max is %s with %i terms' % [lenmax[1], lenmax[0]]

dstr = denommax[0].to_s

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