Solution: Find the Egyptian Fraction
This review provides a detailed analysis of how to convert a fraction to a series of Egyptian Fractions.
We'll cover the following...
Solution #
import mathdef egyptian_fraction(numerator, denominator):"""Finds the egyptian fraction denominators:param numerator: Numerator of the fraction:param denominator: Denominator of the fraction:return: A list of denominators of the egyptian fraction"""# A List to store denominatorlst_denominator = []# While loop runs until fraction becomes 0 i.e,# numerator becomes 0while numerator != 0:# taking ceilingx = math.ceil(denominator / numerator)# storing value in lst_denominator listlst_denominator.append(x)# updating new numerator and denominatornumerator = x * numerator - denominatordenominator = denominator * xreturn lst_denominator# Driver code to test above functionif __name__ == '__main__':print(egyptian_fraction(6, 14))print(egyptian_fraction(2, 3))
Explanation
We can generate Egyptian Fractions using the greedy algorithm. For a given number of the form n/d,
where d > n
, find the greatest possible unit fraction, then perform recursion for the remaining part.
For example, consider . We first find the ceiling of ...