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 a in range(a_min,a_max+1): b_min = max(a+1, int(Fraction(1,(1-sum([Fraction(1,i) for i in [a]])))+1)) b_max = int(Fraction(3,1-sum([Fraction(1,i) for i in [a]]))) for b in range(b_min,b_max+1): c_min = max(b+1, int(Fraction(1,(1-sum([Fraction(1,i) for i in [a,b]])))+1)) c_max = int(Fraction(2,1-sum([Fraction(1,i) for i in [a,b]]))) for c in range(c_min,c_max+1): d = int(Fraction(1,1-sum([Fraction(1,i) for i in [a,b,c]]))) if d>c and 1-sum([Fraction(1,i) for i in [a,b,c,d]])==0: result.append([a,b,c,d]) print result
Of course this has the big disadvantage of being non-generic: unlike the recursive solution, this (without modification) cannot be used to find 5-tuples with the same reciprocal sum of 1.
I tried to write it in a way that emphasizes the repetitive pattern in it: the loop for
b variables are very similar, so maybe that's the part which can be replaced by a well-chosen function from