Introduction
I came across an interesting problem on Twitter: using the numbers 1, 3, 4 and 6, and the operations add, subtract, multiply and divide, create expressions that equal the numbers 1 to 24. Each expression must use 1, 3, 4 and 6 exactly once, but you can use the same operation more than once. At school we had to do something similar with four 4s.
A couple of examples
According to the teacher who described the problem, they have offered to buy pizza for the whole class if they can find expression for each number up to 24 in an hour. Students normally manage to get 1 to 23 in twenty to thirty minutes, but the teacher has never had to buy a pizza.
On reading this I immediately tried to find an expression for 24 and was delighted (and ever so smug) to find it on my first try. The reason I managed was I knew the "trick" from a similar problem for finding an expression for 24 using the numbers 3, 3, 8, 8. Trick isn't the right word though. I saw a few people ask if there was a trick, like using other numbers or something, but there really isn't. It's just that the form of the expression is one that most people wouldn't consider, probably because most expressions of that form will give nasty fractions.
I'll give the answer at the end of this post, but I recommend trying it first.
(Side story: the only time I've interacted with numberphile on Twitter was when he asked for the solution to the 3, 3, 8, 8 problem and I was first to give it. My 15 minutes of microfame.)
Coding a solution
John Wilson suggested that you could write a program to find all possible combinations of expressions, which seemed like an interesting challenge. A naive approach you take all possible permutations of the numbers 1, 3, 4 and 6, and combine them with all possible permutations of operators. However, this would not get the correct answer due to the order in which operations are carried out.
from operator import add, sub, mul, truediv
from itertools import permutations, product
numbers = [1, 3, 4, 6]
operations = [add, sub, mul, truediv]
all_numbers = set(permutations(numbers))
all_operators = product(operations, repeat=len(numbers) - 1)
for nums, ops in product(all_numbers, all_operators):
result = ops[0](nums[0], nums[1])
for i in range(1, len(ops)):
result = ops[i](result, nums[i + 1])In this program, line 7 gets the permutations of numbers. I use a set to remove duplicates in the case of working with 3, 3, 8, 8 etc.. With four unique numbers, there are 24 permutations. On line 8 we generate all the permutations of three operations, allowing for repeats. There are 64 of these. On line 10, we loop through all combinations of numbers and operations. There are $24 \times 64 = 1536$ of these. The program then combines the operations with the numbers (I'm sure there must be a better way to do this). You can then print the result or only print the result if it's 24.
The problem with this code is that it does the operations in order, so for the expression $1 - 3 \times 4 + 6$, the $1 - 3$ is done before the $3 \times 4$. In effect, the expression is $(((1 - 3) \times 4) + 6)$, it will never be able to do $1 - (3 \times 4) + 6$.
What we want is a way to consider the parenthesis in all possible arrangements.
Markus Gerstel quickly came up with a Python solution that solved the problem, however he hard-coded the five different orders of operations. Which got me wondering, how many arrangements are there for $\text{n}$ numbers and how to find them. Markus also had solutions to both these questions. The number of arrangements, is the same as the number of unlabelled binary trees with $\text{n} - 1$ nodes, which is given by the sequence of Catalan numbers.
To be continued...