7
\$\begingroup\$

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 a and b variables are very similar, so maybe that's the part which can be replaced by a well-chosen function from itertools. Any ideas?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for suggesting yield. Indeed that is a more pythonic solution, and I also find it more readable. I agree about passing the arguments even if they are redundant. I would argue about calculating the integer part with the integer division of numerator and denominator is cleaner than int(), but I got your point. Thanks! \$\endgroup\$ – elias Mar 10 '17 at 13:03
  • \$\begingroup\$ I think your calculation of recip_max_denom is incorrect, as you didn't take into account, that the sum has to stay below 1 - in case of 4 terms this means, instead of 1-(1/1+1/2+1/3)=-5/6, 1-(1/2+1/3+1/7)=1/42 should be used. The row has a syntax error because of missing parentheses as well. But I get your idea, thank you very much! \$\endgroup\$ – elias Mar 10 '17 at 13:07
  • \$\begingroup\$ @elias, that's a good point about keeping the sum below the target, and taking that into account I'm not sure how to bound the maximum term without solving the entire problem as a side-effect. One to think about. \$\endgroup\$ – Peter Taylor Mar 10 '17 at 13:25
  • \$\begingroup\$ Well, the upper bound for the denominator can be found with the help of the recursion denom_(n+1)=(denom_n)^2-denom_n+1; denom_1=2, and indeed the terms give one of the valid tuples. \$\endgroup\$ – elias Mar 10 '17 at 13:34
0
\$\begingroup\$

I finally found a method to solve the problem iteratively. The code below is definitely not clean code, it was born to be a proof of concept.

results = []
number_of_integers = 4

first = range(2, number_of_integers+1)
results = [[i] for i in first]
length = 1
while length < number_of_integers-1:
  new_results = []
  for r in results:
    next_min = max(r[-1]+1, int(Fraction(1,(1-sum([Fraction(1,i) for i in r])))+1))
    next_max = int(Fraction(number_of_integers-length,1-sum([Fraction(1,i) for i in r])))
    for next in range(next_min, next_max+1):
      new_results.append(r + [next])
  results = new_results
  length += 1
new_results = []
for r in results:
  last = Fraction(1,(1-sum([Fraction(1,i) for i in r])))
  if last.denominator == 1 and last.numerator>r[-1]:
    new_results.append(r + [last.numerator])
results = new_results
length += 1

print results

The main idea is to keep record of shorter tuples which can be finished to be a solution. That is, we start with tuples of length 1, then append the possible second values to them (so for example with the original version of 4 integers, [2] can be augmented to [2,3], [2,4] and [2,5]), and so on. This loop is repeated until the tuples are only one element short. We than check if the last needed element for the sum satisfies the necessary conditions. No itertools needed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.