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:

³/₄ =  ¹/₂ + ¹/₄

³/₄ =  ¹/₂ + ¹/₅ + ¹/₂₀