Egyptian Fraction Problem

Ancient Egyptians represented each positive fraction as the sum of unique unit fractions. For example, 7/15 = 1/3 + 1/8 + 1/120, or 2/3 = 1/2 + 1/6, or 1/7 = 1/7.

So, your goal is to find such a representation for the number n/m, m, n>0.

That can be reached by using the Greedy Approach. Each time, try to “bite” the number as big as possible to reduce the current value. Let’s look at the 7/15:

• N = 7/15 >= 1/3 – this is the maximum unit fraction we can reach, add it to the answer.

• Now, update the number we’re solving problem for: N = 7/15 – 1/3 = 2/15.

• N = 2/15 >= 1/8 – next maximum unit fraction, add to the answer.

• Update N: N = 2/15 – 1/8 = 1/120.

• N = 1/120 >= 1/120 - add to the answer.

• Update N = 0 -> stop the algorithm.

So, to sum up:

1. Check if the current N == 0. If it is, stop the algorithm.

2. Find the biggest unit fraction less than N and add it to the ans

3. Update value of N by reducing.

The answer is an array f of numbers f[0], f[1], ... , f[t], where f[i] is a divider for fraction 1/f[i]. For our example, answer is [3, 8, 120].

How to find the biggest possible unit fraction It can be easily done for N = n/m by calculating k = math.ceil(m/n). Greater values of k do not give the maximum unit fraction (since, for example, 1/k > 1/(k+1)).