Arithmetic Expressions

By using each of the digits from the set, $\{1, 2, 3, 4\}$, exactly once, and making use of the four arithmetic operations ($+, -, \times, /$) and brackets/parentheses, it is possible to form different positive integer targets.
For example,
\begin{align}
8 &= (4 \times (1 + 3)) / 2\\
14 &= 4 \times (3 + 1 / 2)\\
19 &= 4 \times (2 + 3) – 1\\
36 &= 3 \times 4 \times (2 + 1)
\end{align}
Note that concatenations of the digits, like $12 + 34$, are not allowed.
Using the set, $\{1, 2, 3, 4\}$, it is possible to obtain thirty-one different target numbers of which $36$ is the maximum, and each of the numbers $1$ to $28$ can be obtained before encountering the first non-expressible number.
Find the set of four distinct digits, $a \lt b \lt c \lt d$, for which the longest set of consecutive positive integers, $1$ to $n$, can be obtained, giving your answer as a string: abcd.

This is a challenging problem and there isn’t an apparent straightforward way to solve the problem without the help of a computer. One approach would be to programmatically create all possible expressions that can be made with four distinct numbers and the operators $+, -, \times, /$, parentheses, and check which four digit set has the highest first “non-expressible” number, i.e., the number which cannot be obtained from any of the arithmetic expressions using the four chosen digits exactly once.

Here’s an idea of what the pseudocode would look like to solve this problem:

“`
Max = 0

for a in 0 to 9:
for b in (a+1) to 9:
for c in (b+1) to 9:
for d in (c+1) to 9:
Create all possible expressions using a, b, c, d and operations
Determine the smallest positive integer not expressible from the expressions
If this integer – 1 is greater than Max:
Max = this integer – 1
Answer = a, b, c, d

# The string answer: abcd
StringAnswer = “”
for digit in Answer:
StringAnswer += str(digit)
“`

By implementing code similar to this, one would find that the optimal digits [a, b, c, d] are [1, 2, 5, 8] and the longest set of consecutive positive integers would go from 1 up to 51 before encountering the first non-expressible number 52. Therefore, the answer would be 1258.

Note that there are different ways to create the expressions (e.g., generating all permutations of the four digits, applying each operator in turn), and optimizing the process to ensure it finds the optimal digits in a reasonable time is a challenging task in itself.

More Answers: