4 distinct integers, whose reciprocals sum up to 1

I wrote the following short python program to solve a math puzzle, which asked for all the 4-tuples of distinct natural numbers whose reciprocals sum up to 1.

from fractions import Fraction

results = []

def solve(length, terms):
  previous = terms[-1] if len(terms) > 0 else 0
  sum_needed = 1 - sum([Fraction(1,x) for x in terms])
  if length == len(terms) + 1:
    rest = int(Fraction(1,sum_needed))
    if Fraction(1,rest) == sum_needed and rest >= previous + 1:
      results.append(terms + [rest])
  else:
    next_min = max(previous, int(Fraction(1,sum_needed))) + 1
    next_max = int(Fraction(length,sum_needed))
    for next in range(next_min, next_max+1):
      solve(length, terms + [next])

solve(4,[])
print results

The basic idea is to go through the possible range of the smallest number first, and then based on its value, find the other three numbers.
It all works fine, the output is as desired:

[[2, 3, 7, 42], [2, 3, 8, 24], [2, 3, 9, 18], [2, 3, 10, 15], [2, 4, 5, 20], [2, 4, 6, 12]]

This was a 10-minute project, and not production code, so I don't really worry about readability or maintainability, but still there are a few things which I don't like in my implementation, mostly originating from the recursive approach used.

I've used the itertools module in other tiny hobby-projects, mostly to answer combinatorics-related questions, but I'm not really experienced with other uses of it.

I wonder if changing the approach from recursion to iteration is possible for a problem of this kind, and if itertools has some functions which could help me achieving that.

Any other comments on bad practises in the code above and some pythonic ideas that could have been used in it are also very welcome. Thanks in advance!

I also include an iterative solution:

```
from fractions import Fraction

result = []

a_min = max(1, int(Fraction(1,(1-sum([Fraction(1,i) for i in []])))+1))
a_max = int(Fraction(4,1-sum([Fraction(1,i) for i in []])))
for

Fraction has numerator and denominator, which are cleaner than the mucking around with int().

Appending to an external accumulator is quick and easy, but yield may give more readable code. If you combine that with passing the minimum next denominator and the remaining fraction (rather than respectively extracting them and recalculating them on each call) you get

from fractions import Fraction

def solve(num_terms, min_denom, sum_needed):
  if num_terms == 1:
    if sum_needed.numerator == 1 and sum_needed.denominator >= min_denom:
      yield [sum_needed.denominator]
  else:
    next_min = max(min_denom, int(Fraction(1,sum_needed)) + 1)
    next_max = int(Fraction(num_terms,sum_needed))
    for next in range(next_min, next_max+1):
      yield from [[next] + tail for tail in
                  solve(num_terms - 1, next + 1, sum_needed - Fraction(1, next))]

print (list(solve(4, 1, Fraction(1,1))))

Obviously readability is subjective to some degree, but I prefer the version with yield.

I should note that it would be more Pythonic to use a double comprehension instead of a comprehension inside a loop, but I don't find double comprehensions very readable.

itertools can be used, but I don't think there's any way to do so really efficiently - i.e. with early aborts. I think you would have to bound the maximum possible denominator:

# The largest denominator will be the last term when the previous terms are
# as large as possible
recip_max_denom = 1 - sum([Fraction(1,x) for x in range(1, num_terms)]
max_denom = recip_max_denom.denominator // recip_max_denom.numerator

Then you can use

itertools.combinations(range(1, max_denom + 1), num_terms)

and filter to those which give the correct sum.

StackExchange Code Review Q#157276, answer score: 3