Problem Statement

An   Egyptian fraction   is the sum of distinct unit fractions such as: Each fraction in the expression has a numerator equal to   1   (unity)   and a denominator that is a positive integer,   and all the denominators are distinct   (i.e., no repetitions).
Fibonacci's   Greedy algorithm for Egyptian fractions   expands the fraction

x y

{\displaystyle {\tfrac {x}{y}}}

to be represented by repeatedly performing the replacement

(simplifying the 2nd term in this replacement as necessary, and where

⌈ x ⌉

{\displaystyle \lceil x\rceil }

is the   ceiling   function).

For this task,   Proper and improper fractions   must be able to be expressed.

Proper  fractions   are of the form

a b

{\displaystyle {\tfrac {a}{b}}}

where

a

{\displaystyle a}

and

b

{\displaystyle b}

are positive integers, such that

a < b

{\displaystyle a<b}

,     and improper fractions are of the form

a b

{\displaystyle {\tfrac {a}{b}}}

where

a

{\displaystyle a}

and

b

{\displaystyle b}

are positive integers, such that   a ≥ b.

(See the REXX programming example to view one method of expressing the whole number part of an improper fraction.) For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets [n].

Let's start with the solution:

# 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
}


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]"