Algorithm to compute k fractions of form 1/r summing up to 1

Question

Given k, we need to write 1 as a sum of k fractions of the form 1/r.

For example,

1. For k=2, 1 can uniquely be written as 1/2 + 1/2.
2. For k=3, 1 can be written as 1/3 + 1/3 + 1/3 or 1/2 + 1/4 + 1/4 or 1/6 + 1/3 + 1/2

Now, we need to consider all such set of k fractions that sum upto 1 and return the highest denominator among all such sets; for instance, the sample case 2, our algorithm should return 6.

I came across this problem in a coding competition and couldn't come up with an algorithm for the same. A bit of Google search later revealed that such fractions are called Egyption Fractions but probably they are set of distinct fractions summing upto a particular value (not like 1/2 + 1/2). Also, I couldn't find an algo to compute Egyption Fractions (if they are at all helpful for this problem) when their number is restricted by k.

Answer 1

If all you want to do is find the largest denominator, there's no reason to find all the possibilities. You can do this very simply:

public long largestDenominator(int k){
    long denominator = 1;
    for(int i=1;i<k;i++){
        denominator *= denominator + 1;
    } 
    return denominator;
}

For you recursive types:

public long largestDenominator(int k){
    if(k == 1)
        return 1;
    long last = largestDenominator(k-1);
    return last * (last + 1); // or (last * last) + last)
}

---

Why is it that simple?

To create the set, you need to insert the largest fraction that will keep it under 1 at each step(except the last). By "largest fraction", I mean by value, meaning the smallest denominator.

For the simple case k=3, that means you start with 1/2. You can't fit another half, so you go with 1/3. Then 1/6 is left over, giving you three terms.

For the next case k=4, you take that 1/6 off the end, since it won't fit under one, and we need room for another term. Replace it with 1/7, since that's the biggest value that fits. The remainder is 1/42.

Repeat as needed.

---

For example:

• 2 : [2,2]
• 3 : [2,3,6]
• 4 : [2,3,7,42]
• 5 : [2,3,7,43,1806]
• 6 : [2,3,7,43,1807,3263442]

As you can see, it rapidly becomes very large. Rapidly enough that you'll overflow a long if k>7. If you need to do so, you'll need to find an appropriate container (ie. BigInteger in Java/C#).

It maps perfectly to this sequence:

a(n) = a(n-1)^2 + a(n-1), a(0)=1.

You can also see the relationship to Sylvester's sequence:

a(n+1) = a(n)^2 - a(n) + 1, a(0) = 2

Wikipedia has a very nice article explaining the relationship between the two, as pointed out by Peter in the comments.