## The 147 Puzzle

### February 5, 2013

Today’s exercise comes to us from the world of recreational mathematics:

Find all possible solutions to the equation 1/a + 1/b + 1/c + 1/d + 1/e = 1 where all of a, b, c, d and e are positive integers.

One solution is the trivial 1/5 + 1/5 + 1/5 + 1/5 + 1/5. Another solution, based on the perfect number 1 + 2 + 4 + 7 + 14 = 28, is 1/2 + 1/4 + 1/7 + 1/14 + 1/28. The minimum distinct solution is 1/3 + 1/4 + 1/5 + 1/6 + 1/20, where all the denominators are distinct and the sum of the denominators 3 + 4 + 5 + 6 + 20 = 38 is minimum over all solutions.

Your task is to write a program to enumerate all possible solutions to the equation. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 10 Responses to “The 147 Puzzle”

1. […] today’s Programming Praxis exercise, our goal is to find all combinations of five numbers whose inverses […]

```import Data.Ratio

puzzle :: Integer -> [[Integer]]
puzzle k = f 2 (k%1) 1 where
f _ 1 r = if numerator r == 1 then [[denominator r]] else []
f p n r = concat [map (x : ) \$ f x (n-1) r'
| x <- [p..floor \$ n/r], let r' = r - 1%x, r' > 0]
```
3. Paul said

A recursive Python version.

```from fractions import Fraction
import itertools

def g(n, low, target, prev):
if n == 1:
i = 1 / target
if i.denominator == 1:
print prev + [i.numerator]
else:
for i in itertools.count(low):
fi = Fraction(1, i)
if n * fi < target:
break
t = target - fi
if t > 0:
g(n-1, i, t, prev + [i])

g(4, 2, 1, [])
```
4. Paul said

A cleaner and faster Python version.

```from fractions import Fraction

def g(n, low, target, prev):
invt = 1 / target
if n == 1:
if invt.denominator == 1:
print prev + [invt.numerator]
else:
for i in range(max(low, int(invt) + 1), int(n * invt) + 1):
g(n-1, i, target - Fraction(1, i), prev + [i])

g(4, 2, 1, [])
```
5. […] Pages: 1 2 […]

6. jpverkamp said

Here’s my Racket take:
http://blog.jverkamp.com/2013/02/06/the-147-puzzle/

Essentially, it ended up being a translation of Paul’s second solution into Racket. My original code was close, but I was missing a bit on the recursive bounds.

7. Jussi Piitulainen said

The procedure below passes the denominators of each solution to a
procedure which can be used to count or print them, or it can be
carefully crafted to generate the solutions on demand.

I got all confused about the limits and couldn’t work them out until I
took the hint from jpverkamp and copied the limits from Paul. Then my
procedure began to produce sensible results. I’m still not sure why my
lower limit differs by one from his, but it seems to work this way.
Perhaps it’s my obsession with the empty sum.

```;;; The procedure calls proc on each different sequence of n
;;; increasing denominators d1, ..., dn dk where dk >= min-d
;;; and (+ (/ d1) ... (/ dn)) = x.

(define (for-each-egyptian-sum/minimum-denominator proc x n min-d)
(if (and (zero? x) (zero? n))
(proc)
(if (positive? x)
(do ((dk (max min-d (floor (/ x))) (+ dk 1)))
((< (floor (/ n x)) dk))
(for-each-egyptian-sum/minimum-denominator
(lambda rest (apply proc dk rest))
(- x (/ dk)) (- n 1) dk)))))

(define (test n)
;; counts the ways 1 can be written as n reciprocals
(let ((count 0))
(for-each-egyptian-sum/minimum-denominator
(lambda ds (set! count (+ count 1)))
1 n 1)
count))
```
8. Justin said

I guess recursion is the trickier way to solve this. Why not just iterate?

Also, if you multiply every term by abcde then you get an equation that doesn’t involve division or floats.

for(int a=1; a<10; a++)
{
for(int b=1; b<10; b++)
{
int ab = a*b;
for(int c=1; c<10; c++)
{
int abc = ab*c;
for(int d=1; d<10; d++)
{
int abcd = abc * d;
for(int e=1; e<10; e++)
{
if((b*c*d*e) + (a*c*d*e) + (ab*d*e) + (abc*e) + abcd == abcd*e)
printf("a=%d, b=%d, c=%d, d=%d, e=%d\n", a, b, c, d, e);
}
}
}
}
}

9. Jussi Piitulainen said

Re why not just iterate: The recursive solutions have the number of terms as a parameter. The same procedure, say f, solves f(1), f(2), f(3), f(4), f(5), and f(6). It solves also more, but after 6 the number of solutions becomes large.

Also, the solution to f(5) containing the largest denominator is (2, 3, 7, 43, 1806), so limiting the range of each denominator to single digits hides solutions. I don’t know if there is a way to know upper bounds to all denominators in advance.

None of the posted solutions use floats. They use exact rational arithmetic.

10. Paul said

I think the largest denominator can be calculated (see the function lowest_series below. As you can see the largest denominator becomes very large. In that respect a recursive method works a lot nicer, as the lower and upper bounds can be dermined easily for the remaining terms.

```from operator import mul

def lowest_series(n):
aas = [2, 3]
for i in range(3, n + 1):
an = reduce(mul, aas)
if i < n:
an += 1
aas.append(an)
return aas

for n in range(3, 8):
print n, lowest_series(n)

#3 [2, 3, 6]
#4 [2, 3, 7, 42]
#5 [2, 3, 7, 43, 1806]
#6 [2, 3, 7, 43, 1807, 3263442]
#7 [2, 3, 7, 43, 1807, 3263443, 10650056950806L]
```