Posted on by Kalkicode
Code Greedy

Egyptian Fraction Problem

The Egyptian Fraction Problem is a mathematical challenge that involves expressing a given positive fraction as a sum of unique unit fractions. A unit fraction is a fraction where the numerator is 1. The problem originates from ancient Egypt, where fractions were often represented as sums of unit fractions in various administrative and architectural contexts.

For example, given the fraction 7/53, the Egyptian Fraction representation aims to express it as a sum of unit fractions, such as 1/x1 + 1/x2 + 1/x3 + ..., where x1, x2, x3, ... are positive integers. In this case, the Egyptian Fraction representation of 7/53 is 1/8 + 1/142 + 1/30104.

Problem Statement and Example

Consider the fraction 7/53. The objective is to find an Egyptian Fraction representation for this fraction. We start by breaking down the problem into smaller steps. To solve this problem, we can follow the steps outlined in the provided code.

Idea to Solve the Problem

The basic idea to solve the Egyptian Fraction Problem is to repeatedly find the largest unit fraction (1/x) that is less than or equal to the given fraction, subtract it from the original fraction, and then repeat the process with the remaining fraction until the remaining fraction becomes 0. This can be done by calculating the remainder and divisor at each step.


function egyptianFraction(a, b):
    if a == 0 or b == 0:
    if b >= a:
        remainder = b % a
        divisor = b // a
        if remainder != 0:
            print "1/" + divisor + " + "
            a = a * divisor - b
            b = b * divisor
            egyptianFraction(a, b)
            print "1/" + divisor
        print a // b + " + "
        egyptianFraction(a % b, b)

# Main
a = 7
b = 53
egyptianFraction(a, b)

Algorithm Explanation

  1. Check if either numerator or denominator is 0. If so, return.
  2. If the denominator is greater than or equal to the numerator, calculate remainder and divisor.
  3. If remainder is not 0, print "1/divisor + ", update a and b, and recursively call the function.
  4. If remainder is 0, print "1/divisor".
  5. If denominator is less than numerator, print the integer division result followed by " + " and recursively call the function with updated a and b.

Code Solution

Time Complexity

The time complexity of this algorithm depends on the number of unit fractions needed to represent the given fraction. In the worst case, the algorithm's complexity can be approximated as O(log n), where n is the denominator of the fraction. This is because, at each step, the fraction is divided by an increasingly larger divisor until the remainder becomes 0. The algorithm's complexity is dominated by the division steps and the number of unit fractions needed to represent the fraction.


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment