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

:   :   :   :   1
                2
                +

                1
                3
                +

                1
                16

                (
                =

                43
                48
                )
                {\displaystyle {\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 {\displaystyle {\tfrac {x}{y}}}}
    to be represented by repeatedly performing the replacement

:   :   :   :   x
                y
                =


                1

                ⌈
                y

                /
                x
                ⌉
                +

                (
                −
                y
                )

                mod


                x

                y
                ⌈
                y

                /
                x
                ⌉
                {\displaystyle {\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 {\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 {\displaystyle {\tfrac {a}{b}}}}
    where    

a
{\displaystyle {\displaystyle a}}
    and    

b
{\displaystyle {\displaystyle b}}
    are positive integers, such that    

a
<
b
{\displaystyle {\displaystyle a<b}}
,     and

improper fractions are of the form    

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

a
{\displaystyle {\displaystyle a}}
    and    

b
{\displaystyle {\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 {\displaystyle {\tfrac {43}{48}}}}
   and 

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

  2014
  59
  {\displaystyle {\displaystyle {\tfrac {2014}{59}}}}
* for all proper fractions,    

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

  a
  {\displaystyle {\displaystyle a}}
      and    

  b
  {\displaystyle {\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
* Numberphile YouTube video: Egyptian Fractions and the Greedy Algorithm
assistant
(formerly Perl 6)

```
role Egyptian {
    method gist {
	join ' + ',
	    ("[{self.floor}]" if self.abs >= 1),
	    map {"1/$_"}, self.denominators;
    }
    method denominators {
	my ($x, $y) = self.nude;
	$x %= $y;
	my @denom = gather ($x, $y) = -$y % $x, $y * take ($y / $x).ceiling
	    while $x;
    }
}

say .nude.join('/'), " = ", $_ but Egyptian for 43/48, 5/121, 2014/59;

my @sample = map { $_ => .denominators },
    grep * < 1, 
        map {$_ but Egyptian}, 
            (2 .. 99 X/ 2 .. 99);

say .key.nude.join("/"),
    " has max denominator, namely ",
    .value.max
        given max :by(*.value.max), @sample;

say .key.nude.join("/"),
    " has max number of denominators, namely ",
    .value.elems
        given max :by(*.value.elems), @sample;

```

Output:

```
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 max denominator, namely 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
8/97 has max number of denominators, namely 8
```

Because the harmonic series diverges (albeit very slowly), it is possible to write even improper fractions as a sum of distinct unit fractions. Here is a code to do that:

```
role Egyptian {
    method gist { join ' + ', map {"1/$_"}, self.list }
    method list {
	my $sum = 0;
	gather for 2 .. * {
	    last if $sum == self;
	    $sum += 1 / .take unless $sum + 1 / $_ > self;
	}
    }
}
 
say 5/4 but Egyptian;

```

Output:

```
1/2 + 1/3 + 1/4 + 1/6
```

The list of terms grows exponentially with the value of the fraction, though.