Library · The Fiddler: Solutions · Chapter 152
Can You Order the Operations?
Write an expression using the whole numbers , , , and and the four operations of addition, subtraction, multiplication and division, each number and each operation exactly once, with as many brackets as you like. You may not join digits together, so and cannot make , but fractions are allowed along the way. For example, . What is the largest value you can make?
The Fiddler, Zach Wissner-Gross, July 14, 2023(original post)
The official solution appeared in the post of July 21, 2023 and gives , from , and for the Extra Credit. Both agree with the answers below.
Solution
Addition and multiplication make numbers grow; subtraction and division make them shrink. So the plan is to spend the growing operations on the big numbers and to make the shrinking ones do as little harm as possible.
With one addition and one multiplication, the best use of three numbers is to add the two smaller of them and multiply by the largest: beats , and , because multiplying by the largest number makes the most of the sum.
That leaves , , subtraction and division, all of which must still be used. Subtracting gives , a small loss. But the two leftovers can be spent with no loss at all: , and dividing by changes nothing.
Could subtraction or division ever help? Dividing by a number between and would, and so would subtracting a negative number. But each of those needs its own operation to build the awkward number first, and with only one subtraction and one division there is nothing to spare: a quotient smaller than uses up the only division, and a negative difference uses up the only subtraction. Arguments like this narrow the field but do not, by themselves, rule out every bracketing, and that last step is left to the exhaustive search below. It confirms that nothing beats
The computation
The search builds every value that every bracketing can produce. For each group of numbers and each collection of operations, it splits the group into two smaller groups in every way, gives each part its share of the operations, and combines every value of one part with every value of the other using the remaining operation, in both orders. Remembering the results for each group keeps this fast. Exact fractions are used throughout, and one expression is kept for each value so that the winner can be read off.
from fractions import Fraction
from functools import lru_cache
from itertools import combinations
def apply(op, a, b):
if op == "+": return a + b
if op == "-": return a - b
if op == "*": return a * b
return a / b if b else None # no dividing by zero
def without(items, taken):
rest = list(items)
for x in taken:
rest.remove(x)
return tuple(rest)
@lru_cache(maxsize=None)
def values(nums, ops):
"""Map each value of an expression using each number in
nums and each operation in ops once to one expression."""
if len(nums) == 1:
return {Fraction(nums[0]): str(nums[0])}
out = {}
for k in range(1, len(nums)):
for left in set(combinations(nums, k)):
right = without(nums, left)
for op in set(ops):
rest = without(ops, [op])
for lops in set(combinations(rest, k - 1)):
A = values(left, lops)
B = values(right, without(rest, lops))
for a, ea in A.items():
for b, eb in B.items():
v = apply(op, a, b)
if v is not None and v not in out:
out[v] = f"({ea} {op} {eb})"
return out
ops = ("*", "+", "-", "/") # sorted, as values expects
best = max(values((1, 2, 3, 4, 5), ops).items())
print("largest value:", best[0], "from", best[1])It prints
largest value: 35 from (5 * (3 + (4 / (2 - 1))))The search happened to record a slightly different bracketing, , which also uses each number and operation once and also makes .
Extra Credit
Now use the nine numbers to , each once, and each of the four operations exactly twice. What is the largest value you can make?
Solution
With two of each operation, subtraction and division change sides. Two subtractions can make an addition: , at the cost of subtracting one number. Two divisions can make a multiplication: , at the cost of the number , which is of little use in a product anyway.
So think of the expression as a product of four factors: the two multiplications, plus the one made from the divisions. The numbers to must be gathered into these four factors, and gathering takes merges: the two additions merge two pairs, and the double subtraction merges three numbers, one of them subtracted. That shapes the factors as two pairs, one triple and one single number. The subtracted number should be the smallest available, , so the eight numbers, which add up to , contribute to the four factors.
A product with a fixed total is largest when the factors are as equal as possible. Here one factor is a single number, at most , so the best is to make it and split the remaining as evenly as whole numbers allow, into , and . One way to do it:
The argument above assumes the shape of the best expression rather than proving it; other shapes, such as dividing by a difference of fractions, are not ruled out by it. The exhaustive search below settles the matter.
The question also asks about the numbers to with each operation used times. For and the answers are and . For larger the search space explodes; the official write-up reports constructions found by solvers, such as for , without a proof that they are best.
The computation
The same idea as before, building the values of every group of numbers from smaller groups, is far too slow to run naively here: the groups of eight numbers have tens of millions of values each. The search therefore keeps less where it can.
Store every value, as an exact fraction, for groups of up to seven numbers, built as above with vectorised arithmetic.
For the whole expression, split the nine numbers into two groups. If both have at most seven numbers, find the largest value of the top operation from the two value lists: the largest sum, difference, product or quotient can be read off from the extremes of one list and the entries of the other.
If one group has eight numbers, the other is a single number . Then , , , and need only the largest and smallest values of the eight-number group , and needs its least positive value. Those three numbers are found from the splits of into smaller groups, searching the sorted value lists near zero for the least positive one.
The program takes about two minutes.
import numpy as np
from fractions import Fraction
from itertools import product
NUMS = range(1, 10)
FULL = (1 << 9) - 1
TOTAL = (2, 2, 2, 2) # uses of + - * /
def size(mask):
return bin(mask).count("1")
def splits(mask): # unordered two-way splits
low, sub = mask & -mask, (mask - 1) & mask
while sub:
if sub & low:
yield sub, mask ^ sub
sub = (sub - 1) & mask
def op_splits(ops, n1, n2):
"""Top operation, then the uses left for each side."""
for op in range(4):
if ops[op]:
rest = list(ops)
rest[op] -= 1
for o1 in product(*(range(x + 1) for x in rest)):
o2 = tuple(r - x for r, x in zip(rest, o1))
if sum(o1) == n1 - 1 and sum(o2) == n2 - 1:
yield op, o1, o2
def reduce(p, q): # exact fractions p/q
keep = q != 0
p, q = p[keep], q[keep]
s = np.where(q < 0, -1, 1)
g = np.gcd(p, q)
return s*p//g, s*q//g
def combine(A, B, op):
"""All values a op b and b op a, as exact fractions."""
a, b = A[0][:, None], B[0][None, :]
c, d = A[1][:, None], B[1][None, :]
big = max(abs(a).max()*d.max(), abs(b).max()*c.max())
assert big < 2**31 # no overflow in int64
if op == 0:
p, q = a*d + b*c, c*d
elif op == 1:
p = np.r_[(a*d - b*c).ravel(), (b*c - a*d).ravel()]
q = np.r_[(c*d).ravel(), (c*d).ravel()]
elif op == 2:
p, q = a*b, c*d
else:
p = np.r_[(a*d).ravel(), (b*c).ravel()]
q = np.r_[(c*b).ravel(), (d*a).ravel()]
return reduce(np.ravel(p), np.ravel(q))
def unique(p, q): # sorted by value
v = p/q
i = np.lexsort((q, p))
p, q, v = p[i], q[i], v[i]
new = np.r_[True, (p[1:] != p[:-1]) | (q[1:] != q[:-1])]
p, q, v = p[new], q[new], v[new]
i = np.argsort(v, kind="stable")
return p[i], q[i], v[i]
memo = {}
def values(mask, ops):
"""Every value from the numbers in mask, using the
operations exactly as counted in ops."""
if (mask, ops) in memo:
return memo[mask, ops]
if size(mask) == 1:
x = np.array([mask.bit_length()], np.int64)
res = (x, np.ones(1, np.int64), x.astype(float))
else:
parts = [combine(values(s, o1), values(t, o2), op)
for s, t in splits(mask) for op, o1, o2
in op_splits(ops, size(s), size(t))]
p = np.concatenate([x[0] for x in parts] or [[]])
q = np.concatenate([x[1] for x in parts] or [[]])
res = unique(p.astype(np.int64), q.astype(np.int64))
if size(mask) <= 6:
memo[mask, ops] = res
return res
def exact(S, i):
return Fraction(int(S[0][i]), int(S[1][i]))
def near(S, x):
"""Exact values of S on either side of the float x."""
i = int(np.searchsorted(S[2], x))
return [exact(S, j) for j in range(max(i - 2, 0),
min(i + 2, len(S[2])))]
def best_ratio(e, A, pick):
"""Exact max (pick=max) or min of e / a over nonzero a."""
nz = np.flatnonzero(A[2])
r = float(e)/A[2][nz]
top = pick(r)
close = nz[np.abs(r - top) <= 1e-9*abs(top) + 1e-300]
return pick(e/exact(A, i) for i in close)
def extremes(A, B, op):
"""Largest, smallest and least positive values of a op b
and b op a, for a in A and b in the (smaller) set B."""
bs = [exact(B, j) for j in range(len(B[2]))]
ends = [exact(A, 0), exact(A, -1)]
if op == 0:
top, low = ends[1] + bs[-1], ends[0] + bs[0]
out = [x + b for b in bs for x in near(A, -float(b))]
elif op == 1:
top = max(ends[1] - bs[0], bs[-1] - ends[0])
low = -top
out = [s*(x - b) for b in bs for x in near(A, float(b))
for s in (1, -1)]
elif op == 2:
c = [x*y for x in ends for y in (bs[0], bs[-1])]
top, low = max(c), min(c)
a0, b0 = near(A, 0.0), near(B, 0.0)
out = [x*y for x in a0 for y in b0]
else:
c = [x/b for b in bs if b for x in ends]
c += [best_ratio(e, A, f) for e in (bs[0], bs[-1])
for f in (max, min)]
top, low = max(c), min(c)
a0, b0 = near(A, 0.0), near(B, 0.0)
out = [x/y for x in a0 for y in (bs[0], bs[-1]) if y]
out += [x/y for x in b0 for y in ends if y]
pos = [v for v in out if v > 0]
return top, low, min(pos) if pos else None
def opvecs(n): # ways to use n operations
return [o for o in product(range(3), repeat=4)
if sum(o) == n]
best, stats = Fraction(0), {}
def note(key, top, low, least):
t, l, m = stats.get(key, (top, low, least))
both = [x for x in (m, least) if x]
m = min(both) if both else None
stats[key] = (max(t, top), min(l, low), m)
# The 8-number subexpressions, split no worse than 6 + 2.
for m8 in (FULL ^ (1 << k) for k in range(9)):
for o8 in opvecs(7):
for s, t in splits(m8):
if max(size(s), size(t)) > 6:
continue
for op, o1, o2 in op_splits(o8, size(s), size(t)):
A, B = values(s, o1), values(t, o2)
if len(A[2]) < len(B[2]):
A, B = B, A
if len(B[2]):
note((m8, o8), *extremes(A, B, op))
# Each 7-number set once: top-level 7 + 2 splits, 8 = 7 + 1.
for s, t in splits(FULL):
if size(s) != 7 and size(t) != 7:
continue
m7, m2 = (s, t) if size(s) == 7 else (t, s)
for o7 in opvecs(6):
A = values(m7, o7)
if not len(A[2]):
continue
for op, o1, o2 in op_splits(TOTAL, 7, 2):
if o1 == o7 and len(values(m2, o2)[2]):
top = extremes(A, values(m2, o2), op)[0]
best = max(best, top)
for y in (m2 & -m2, m2 ^ (m2 & -m2)):
for o8 in opvecs(7):
for op, o1, o2 in op_splits(o8, 7, 1):
if o1 == o7:
note((m7 | y, o8),
*extremes(A, values(y, o2), op))
# Top level from the remaining splits: 6 + 3, 5 + 4, 8 + 1.
for s, t in splits(FULL):
if max(size(s), size(t)) in (6, 5):
for op, o1, o2 in op_splits(TOTAL, size(s), size(t)):
A, B = values(s, o1), values(t, o2)
if len(A[2]) < len(B[2]):
A, B = B, A
if len(B[2]):
best = max(best, extremes(A, B, op)[0])
for (m8, o8), (top, low, least) in stats.items():
x = Fraction((FULL ^ m8).bit_length())
op = [a - b for a, b in zip(TOTAL, o8)].index(1)
c = [[top + x], [top - x, x - low], [top*x, low*x],
[top/x, low/x] + ([x/least] if least else [])][op]
best = max([best] + c)
print("largest value:", best)It prints
largest value: 9900