Greedy Algorithm for Egyptian Fraction

In early Egypt, people used to use only unit fraction (in the form of (1/n)) to represent the decimal numbers.

The fraction was always written in the form 1/n , where the numerator is always 1 and denominator is a positive number. All other fractions were represented as the summation of the unit fractions. For example, 3/4 = 1/2 1/4.

Given a positive fraction, write it in the form of summation of unit fractions.

Example:
2/3 = 1/2 1/6
6/14 = 1/3 1/11 1/231
12/13 = 1/2 1/3 1/12 1/156

Greedy Solution:

For a given number of the form ‘nr/dr’ where dr > nr, first find the greatest possible unit fraction, then call the function recursively for the remaining part.

For example, consider 6/14. First find ceiling of 14/6, i.e., 3. The first unit fraction becomes 1/3.

The remaining fraction is 6/14 – 1/3 = 4/42. Now repeat the same algorithm for 4/42. The ceiling of 42/4 is 11. So the next unit fraction is 1/11.

Now we are left with 4/42 – 1/11 = 1/231. This is a unit fraction itself. So we stop the recursion. We stop when the result is a unit fraction.

6/14 = 1/3 1/11 1/231

class Egyptian Fraction
{
static void printEgyptian(int nr, int dr)
{
if (0 == nr || 0 == dr)
return;

// IF nr IS MULTIPLE OF nr. THEN NOT A FRACTION
if (nr % dr == 0)
{
System.out.print(nr / dr);
return;
}

// IF ALREADY A UNIT FRACTION. OR CAN BE DIRECTLY CONVERTED TO IT.
// i.e dr divisible by nr
if (dr % nr == 0)
{
System.out.print("1/" dr / nr);
return;
}

if (nr > dr)
{
System.out.print(nr / dr " ");
printEgyptian(nr % dr, dr);
return;
}

// PRINT ceiling(dr/nr) AS CURRENT FRACTION
int n = dr/nr 1;
System.out.print("1/" n " ");

// Recur for remaining part
printEgyptian(nr * n - dr, dr * n);
}
}

Note that there exists multiple solution to the same fraction. For example:

3/4 =  1/2   1/4

3/4 =  1/2   1/5  1/20