# Baez’s “42” – Solving the first puzzle

In a blog post, John Baez proposes the following puzzle:

Consider solutions of

$\displaystyle \frac{1}{p} + \frac{1}{q} + \frac{1}{r} = \frac{1}{2}$

with positive integers $p \le q \le r,$ and show that the largest possible value of $r$ is $42$.

We can start by writing the following simple Python program to solve the problem, using integer arithmetic to avoid floating point problems:

from itertools import count
for r in count(1):
for q in xrange(1, r + 1):
for p in xrange(1, q + 1):
# 1/p + 1/q + 1/r = 1/2
# qr + pr + pq = pqr/2
# 2(qr + pr + pq) = pqr
if 2*(q*r + p*r + p*q) == p*q*r:
print p, q, r


This program shows us ten possible values (including 42 in the last triple),

6 6 6
4 8 8
5 5 10
4 6 12
3 12 12
3 10 15
3 9 18
4 5 20
3 8 24
3 7 42


but, as it’s trying to enumerate all integer triples, it doesn’t halt.

To be sure not to miss any interesting integer triple, we must explore them more carefully:

from itertools import count
for p in count(1):
# checks if we are leaving room for 1/q + 1/r
# 1/p >= 1/2
if 2 >= p:
continue # we need smaller values of 1/p
# checks if we can reach 1/2 with the biggest legal values for 1/q and 1/r
# 1/p + 1/p + 1/p < 1/2
if 3 * 2 < p:
break
for q in count(p):
# checks if we are leaving room for 1/r
# 1/p + 1/q >= 1/2
if 2 * (q + p) >= p * q:
continue
# checks if we can reach 1/2 with the biggest legal value for 1/r
# 1/p + 1/q + 1/q < 1/2
if 2 * (q + 2 * p) < p * q:
break
for r in count(q):
lhs = 2 * (q * r + p * r + p * q)
rhs = p * q * r
# 1/p + 1/q + 1/r > 1/2
if lhs > rhs:
continue
# 1/p + 1/q + 1/r < 1/2
elif lhs < rhs:
break
# 1/p + 1/q + 1/r = 1/2
else:
print p, q, r


The results are the same, but now we can be sure of having the whole solution.

# A simple combinatorics problem

To break the long hiatus, I’m going to solve a short combinatorics problem extracted from “A Walk Through Combinatorics”:

Find all positive integers $a < b < c$ such that $\frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 1$.

As $a$ is the smallest of the three integers, we know that $\frac{1}{a}$ will be the bigger of the three fractions. The three fractions must add to one and they must be different, so $\frac{1}{a}$ must be equal to $\frac{1}{2}$. Rewriting the restriction using this newly found knowledge:

$\displaystyle \frac{1}{2} + \frac{1}{b} + \frac{1}{c} = 1$

$\displaystyle \frac{1}{b} + \frac{1}{c} = \frac{1}{2}$.

$b$ must be greater than 2, but it cannot be bigger than 3 because, otherwise,

$\displaystyle \frac{1}{b} + \frac{1}{c} \leq \frac{1}{4} + \frac{1}{5} = \frac{9}{20} < \frac{1}{2}$.

Then we have $b = 3$ and

$\displaystyle c = \frac{1}{1 - \frac{1}{2} - \frac{1}{3}} = 6$.