An   Egyptian fraction   is the sum of distinct unit fractions such as:

  






1
2



+



1
3



+



1
16




(
=



43
48



)


{\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{16}}\,(={\tfrac {43}{48}})}

 
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

  





x
y


=


1

⌈
y

/

x
⌉



+



(
−
y
)





mod


x


y
⌈
y

/

x
⌉





{\displaystyle {\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil }}}

 


(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].



Task requirements

   show the Egyptian fractions for: 






43
48





{\displaystyle {\tfrac {43}{48}}}

 and 






5
121





{\displaystyle {\tfrac {5}{121}}}

 and 






2014
59





{\displaystyle {\tfrac {2014}{59}}}


   for all proper fractions,    






a
b





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

    where    



a


{\displaystyle a}

    and    



b


{\displaystyle b}

    are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
   the largest number of terms,
   the largest denominator.
   for all one-, two-, and three-digit integers,   find and show (as above).     {extra credit}


Also see

   Wolfram MathWorld™ entry: Egyptian fraction


with javascript_semantics 
include mpfr.e
function egyptian(integer num, denom)
    mpz n = mpz_init(num),
        d = mpz_init(denom),
        t = mpz_init()
    sequence result = {}
    while mpz_cmp_si(n,0)!=0 do
        mpz_cdiv_q(t, d, n)
        result = append(result,"1/"&mpz_get_str(t))
        mpz_neg(d,d)
        mpz_mod(n,d,n)
        mpz_neg(d,d)
        mpz_mul(d,d,t)
    end while
    {n,d} = mpz_free({n,d})
    return result
end function
 
procedure efrac(integer num, denom)
    string fraction = sprintf("%d/%d",{num,denom}),
           prefix = ""
    if num>=denom then
        integer whole = floor(num/denom)
        num -= whole*denom
        prefix = sprintf("[%d] + ",whole)
    end if
    string e = join(egyptian(num, denom)," + ")
    printf(1,"%s -> %s%s\n",{fraction,prefix,e})
end procedure
 
efrac(43,48)
efrac(5,121)
efrac(2014,59)
 
integer maxt = 0, 
        maxd = 0
string maxts = "",
       maxds = "",
       maxda = ""
 
for r=98 to 998 by 900 do   -- (iterates just twice!)
    sequence sieve = repeat(repeat(false,r+1),r) -- to eliminate duplicates
    for n=1 to r do
        for d=n+1 to r+1 do
            if sieve[n][d]=false then
                string term = sprintf("%d/%d",{n,d})
                sequence terms = egyptian(n,d)
                integer nterms = length(terms)
                if nterms>maxt then
                    maxt = nterms
                    maxts = term
                elsif nterms=maxt then
                    maxts &= ", " & term
                end if
                integer mlen = length(terms[$])-2
                if mlen>maxd then
                    maxd = mlen
                    maxds = term
                    maxda = terms[$]
                elsif mlen=maxd then
                    maxds &= ", " & term
                end if
                if n<r/2 then
                    for k=2 to 9999 do
                        if d*k > r+1 then exit end if
                        sieve[n*k][d*k] = true
                    end for
                end if
            end if
        end for
    end for
    printf(1,"\nfor proper fractions with 1 to %d digits\n",{length(sprint(r))})
    printf(1,"Largest number of terms is %d for %s\n",{maxt,maxts})
    maxda = maxda[3..$] -- (strip the "1/")
    maxda[6..-6]="..."  -- (show only first/last 5 digits)
    printf(1,"Largest size for denominator is %d digits (%s) for %s\n",{maxd,maxda,maxds})
end for
