Introduction

This is a classic Egyptian-fraction problem: write 1 as a sum of exactly k unit fractions of the form 1 / r. The most important clarification is whether denominators may repeat, because the construction is different in the repeated and distinct cases.

Start With The Small Cases

If repetition is allowed, then some cases are immediate. For k = 2:

1 = 1/2 + 1/2

If denominators must be distinct, k = 2 has no positive-integer solution, but k = 3 does:

1 = 1/2 + 1/3 + 1/6

That identity is the usual base case for constructive proofs. Once you have one correct decomposition, the goal is to increase the number of terms without changing the sum.

The Key Splitting Identity

The standard trick is this identity:

1/n = 1/(n + 1) + 1/(n(n + 1))

You can verify it with a common denominator:

11/(n + 1) + 1/(n(n + 1))
2= n/(n(n + 1)) + 1/(n(n + 1))
3= (n + 1)/(n(n + 1))
4= 1/n

Each time you apply this identity, one term becomes two terms. The total sum stays the same, so the number of unit fractions increases by exactly one.

A Constructive Algorithm For Distinct Denominators

For distinct denominators, start from:

1 = 1/2 + 1/3 + 1/6

If you need more than three terms, repeatedly replace the current largest denominator n with:

1/n -> 1/(n + 1) + 1/(n(n + 1))

This works because both new denominators are larger than n. If you always split the largest existing denominator, the new values will not collide with any earlier, smaller denominator, so distinctness is preserved.

For example, to get four terms, split 1 / 6:

1 = 1/2 + 1/3 + 1/7 + 1/42

To get five terms, split 1 / 42:

1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1806

That already gives an inductive algorithm for every k >= 3.

Python Implementation

The construction maps naturally to code. Using exact fractions avoids floating-point mistakes when verifying the result.

1from fractions import Fraction
2
3
4def unit_fractions_for_one(k: int, distinct: bool = True) -> list[int]:
5    if k < 1:
6        raise ValueError("k must be positive")
7
8    if not distinct:
9        return [k] * k
10
11    if k == 1:
12        return [1]
13    if k == 2:
14        raise ValueError("no distinct positive solution exists for k = 2")
15
16    denominators = [2, 3, 6]
17
18    while len(denominators) < k:
19        n = denominators.pop()
20        denominators.append(n + 1)
21        denominators.append(n * (n + 1))
22        denominators.sort()
23
24    return denominators
25
26
27def verify(denominators: list[int]) -> Fraction:
28    total = sum(Fraction(1, d) for d in denominators)
29    return total
30
31for k in range(3, 7):
32    ds = unit_fractions_for_one(k, distinct=True)
33    print(k, ds, verify(ds))

If you allow repeated denominators, the case is even simpler. Since k * (1 / k) = 1, the list [k, k, ..., k] with k copies always works. The harder and more interesting version is the distinct case, which is why most discussions focus on the splitting identity.

Why The Algorithm Works

The proof is short and constructive:

1. The base case 1 = 1/2 + 1/3 + 1/6 is correct.
2. Each splitting step replaces one term 1/n with two terms that sum to the same value.
3. Therefore the total sum stays equal to 1 after every step.
4. If you split the largest denominator, the new denominators are larger and remain distinct from the earlier ones.

That is enough for an induction on the number of terms. Starting at three terms, you can build four, then five, and so on.

Complexity And Practical Notes

The algorithm is simple, but the denominators grow very quickly. After a few splits, values become large because of the multiplication by n(n + 1). For a proof or a contest problem, that is usually fine. For a production system that must print compact decompositions, you may want a different objective function, such as minimizing the largest denominator.

Still, for the specific task "produce any valid representation with exactly k unit fractions," this construction is hard to beat. It is deterministic, easy to prove correct, and easy to implement.

Why The Greedy Egyptian-Fraction Algorithm Is Different

The classic greedy Egyptian-fraction algorithm also writes rationals as sums of unit fractions, but it is designed to terminate with some decomposition, not to produce exactly k terms. If the requirement is "exactly k fractions," the splitting identity is the right tool because each application increases the count by one in a controlled way.

That direct control is the main reason this construction is taught for the exact-term-count version of the problem.

Common Pitfalls

• Forgetting to ask whether repeated denominators are allowed.
• Assuming k = 2 has a distinct positive solution when it does not.
• Using the greedy Egyptian-fraction algorithm even though it does not control the final number of terms.
• Splitting arbitrary denominators and then accidentally creating duplicates.
• Verifying the result with floating-point arithmetic instead of exact rational arithmetic.

Summary

• The key identity is 1 / n = 1 / (n + 1) + 1 / (n(n + 1)).
• If repeats are allowed, k copies of 1 / k always sum to 1.
• For distinct denominators, 1 = 1/2 + 1/3 + 1/6 is the standard base case.
• Repeatedly splitting the largest denominator gives a valid construction for every k >= 3.
• Exact arithmetic is the safest way to verify the output in code.