Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
m (tinker with formula rendering) |
(→Tcl: Added implementation) |
||
Line 241: | Line 241: | ||
largest number of terms in the Egyptian fractions used is 13 terms for 529/914 |
largest number of terms in the Egyptian fractions used is 13 terms for 529/914 |
||
largest denominator in the Egyptian fractions is 2847 digits is for 36/457 |
largest denominator in the Egyptian fractions is 2847 digits is for 36/457 |
||
</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 |
|||
</pre> |
</pre> |