Question

Using Python 3.7 and higher, implement function egypt(numerator, denominator) that uses the greedy strategy to determine a set of distinct Egyptian fractions that sum to numerator/denominator. You cannot use any sort of division, including the floor and ceiling methods, nor the division, remainder, or modulus operators.

1. Implement function egypt(numerator, denominator) that uses the greedy strategy presented in slides 7 and 8 of Lecture 30 (April 13) to determine a set of distinct (i.e. all different) Egyptian fractions that sum to numerator/denominator. You may assume numerator and denominator are positive integers and that numerator is less than or equal to denominator. Your function should both 1) print a readable "equation" showing the result (see examples below) and 2) return a list of Egyptian fraction denominators Examples: >>> egypt (4,5) 4/5 = 1/2 + 1/4 + 1/20 [2, 4, 20] >>> egypt (2,11) 2/11 = 1/6 + 1/66 [6, 66) >>> egypt (761, 1000) 761/1000 = 1/2 + 1/4 + 1/91 + 1/91000 [2, 4, 91, 91000) Important note: you may NOT use division in your function. All calculations should be done with integers. In particular, computing the difference (n/d) - (1/C) is a key step (see slide 8). You can calculate an integer numerator and integer denominator for this difference using only multiplication and subtraction.

Answer 1

• Below is the implementation of the code for finding egyptian function in python without using any division or modulo operators, and using a greedy method where fraction has numerator always less than denominator but non-zero.
• For better understanding please refer to the comments mentioned in the code.
• CODE:

#function to calculate ceil of a fraction without using division
def calc(num, den):
count=0
for i in range(1,1000000):
count+=1
if (num*i)>=den:
break
return count

#function to find egytian fractions for a particular fraction with numerator num and denominator den where den>num
def egypt(num, den):
#print given fraction using shown format
print("{0}/{1} =". format(num, den), end=" ")

#list to store answers of our differenr denominators
denominators = []
  
#loop till our fraction becomes 0 i.e, num becomes 0.
while num != 0:
  
#calculate ceil of (den/num) without using division or modulo
x=calc(num, den)
#append value of denominator in the list
denominators.append(x)
  
#update our numerator and denominator
num = x*num - den
den = den*x
#printing the obtained fractions
for i in range(len(denominators)):
if i != len(denominators)-1:
print("1/{0} +" . format(denominators[i]), end = " ")
else:
print("1/{0}" . format(denominators[i]))
#printing list of denominators
print(denominators)

egypt(4, 5)
egypt(2, 11)
egypt(761, 1000)

• Output:4/5 = 1/2 + 1/4 + 1/20
  [2, 4, 20]
  2/11 = 1/6 + 1/66
  [6, 66]
  761/1000 = 1/2 + 1/4 + 1/91 + 1/91000
  [2, 4, 91, 91000]
• For better clarity of the indentation below is the attached picture of the code and it's output.

So if you have any doubt regarding this please feel free to ask in the comment section and if it is helpful then please up vote this solution, THANK YOU.