Greedy algorithm for Egyptian fractions: Difference between revisions

</pre>

=={{header|Tcl}}==

<lang tcl># Just compute the denominator terms, as the numerators are always 1

proc egyptian {num denom} {

set result {}

while {$num} {

# Compute ceil($denom/$num) without floating point inaccuracy

set term [expr {$denom / $num + ($denom/$num*$num < $denom)}]

lappend result $term

set num [expr {-$denom % $num}]

set denom [expr {$denom * $term}]

}

return $result

}</lang>

Demonstrating:

{{works with|Tcl|8.6}}

<lang tcl>package require Tcl 8.6

proc efrac {fraction} {

scan $fraction "%d/%d" x y

set prefix ""

if {$x > $y} {

set whole [expr {$x / $y}]

set x [expr {$x - $whole*$y}]

set prefix "\[$whole\] + "

}

return $prefix[join [lmap y [egyptian $x $y] {format "1/%lld" $y}] " + "]

}

foreach f {43/48 5/121 2014/59} {

puts "$f = [efrac $f]"

}

set maxt 0

set maxtf {}

set maxd 0

set maxdf {}

for {set d 1} {$d < 100} {incr d} {

for {set n 1} {$n < $d} {incr n} {

set e [egyptian $n $d]

if {[llength $e] >= $maxt} {

set maxt [llength $e]

set maxtf $n/$d

}

if {[lindex $e end] > $maxd} {

set maxd [lindex $e end]

set maxdf $n/$d

}

}

}

puts "$maxtf has maximum number of terms = [efrac $maxtf]"

puts "$maxdf has maximum denominator = [efrac $maxdf]"</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

8/97 has maximum number of terms = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

8/97 has maximum denominator = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665