...

/

Solution: Find the Egyptian Fraction

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 math
def 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 denominator
lst_denominator = []
# While loop runs until fraction becomes 0 i.e,
# numerator becomes 0
while numerator != 0:
# taking ceiling
x = math.ceil(denominator / numerator)
# storing value in lst_denominator list
lst_denominator.append(x)
# updating new numerator and denominator
numerator = x * numerator - denominator
denominator = denominator * x
return lst_denominator
# Driver code to test above function
if __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 6/146/14. We first find the ceiling of 14/6\lceil 14/6 \rceil ...