An Egyptian fraction is the sum of finitely many rational numbers, each of which can be expressed in the form
1/q where q is an integer.
For example, the Egyptian fraction 61/66 is written as 1/2 + 1/3 + 1/11
Every positive fraction can be represented as sum of unique unit fractions. A fraction is unit fraction if numerator is 1 and denominator is a positive integer, for example 1/3 is a unit fraction. Such a representation is called Egyptian Fraction as it was used by ancient Egyptians.
Following are few examples:
Egyptian Fraction Representation of 2/3 is 1/2 + 1/6 Egyptian Fraction Representation of 6/14 is 1/3 + 1/11 + 1/231 Egyptian Fraction Representation of 12/13 is 1/2 + 1/3 + 1/12 + 1/156
We can generate Egyptian Fractions using Greedy Algorithm. For a given number of the form nr/dr where dr > nr, first find the greatest possible unit fraction, then recur for the remaining part. For example, consider 6/14, we first find ceiling of 14/6, i.e., 3. So the first unit fraction becomes 1/3, then recur for (6/14 %u2013 1/3) i.e., 4/42.
Find the Egyptian fraction representation of 8/9
The greatest unit fraction less than 8/9 is 1/2%u200B.
The remainder is 7/18
The greatest unit fraction less than 7/18 is 1/3.
The remainder is 1/18.
This is a unit fraction, so the answer is given by
7/18= 1/2 + 1/3 + 1/18
// C++ program to print a fraction in Egyptian Form using Greedy
void findEgyptian(int nr,int dr)
if(dr ==0|| nr ==0)
cout <<"1/"<< dr/nr;
cout << nr/dr;
if(nr > dr)
cout << nr/dr <<" + ";
int n = dr/nr +1;
cout <<"1/"<< n <<" + ";
cout<<"Egyptian Fraction Representation of"<<nr<<"/"<<dr<<" is \n";