Project Euler Problem 93

Solution

Answer: 1258

We must search over all 4-digit sets ${a,b,c,d} \subset {0,\dots,9}$, and for each set determine which positive integers can be formed using:

• each digit exactly once,
• the operations $+,-,\times,/$,
• arbitrary parenthesization.

The goal is to maximize the length of the consecutive run

$$1,2,3,\dots,n$$

starting from $1$.

---

Mathematical analysis

Suppose we pick four distinct digits $a,b,c,d$.

To build expressions:

1. Arrange the digits in any order.
2. Insert three operations chosen from:

$$+,-,\times,/$$ 3. Parenthesize in every valid binary-tree form.

---

Step 1 — Permutations of digits

There are

$$4! = 24$$

ways to order the digits.

Example with $1,2,3,4$:

$$(1,2,3,4), (1,2,4,3), \dots$$

---

Step 2 — Choices of operators

Each of the three operator slots has 4 choices, so:

$$4^3 = 64$$

operator combinations.

Example:

$$(+,\times,-)$$

corresponds to something like

$$a + b \times c - d$$

before parenthesization.

---

Step 3 — Parenthesizations

With four operands there are exactly five binary parenthesization structures:

$$\begin{aligned} 1.;& ((a;b);c);d \ 2.;& (a;(b;c));d \ 3.;& (a;b);(c;d) \ 4.;& a;((b;c);d) \ 5.;& a;(b;(c;d)) \end{aligned}$$

These correspond to all full binary trees on four leaves (Catalan number $C_3=5$).

---

Step 4 — Exact arithmetic

Division creates fractions, so floating-point arithmetic is dangerous due to rounding errors.

Instead, use exact rational arithmetic via Python’s Fraction.

Example:

$$\frac{1}{3} + \frac{1}{6} = \frac12$$

is represented exactly.

---

Step 5 — Collect positive integers

For every generated value:

• denominator must equal $1$,
• value must be positive.

Store all reachable integers in a set.

Then compute the longest consecutive prefix beginning at $1$.

Example:

If reachable integers are

$${1,2,3,4,5,6,7,8,9,10,12}$$

then the consecutive run length is $10$.

---

Python implementation

from itertools import combinations, permutations, product
from fractions import Fraction

# Apply an arithmetic operation safely
def apply_op(x, y, op):
    if op == '+':
        return x + y
    if op == '-':
        return x - y
    if op == '*':
        return x * y
    if op == '/':
        if y == 0:
            return None
        return x / y

# Evaluate all 5 parenthesization patterns
def generate_values(nums, ops):
    a, b, c, d = map(Fraction, nums)
    op1, op2, op3 = ops

    results = []

    # 1. ((a b) c) d
    r1 = apply_op(a, b, op1)
    if r1 is not None:
        r2 = apply_op(r1, c, op2)
        if r2 is not None:
            r3 = apply_op(r2, d, op3)
            if r3 is not None:
                results.append(r3)

    # 2. (a (b c)) d
    r1 = apply_op(b, c, op2)
    if r1 is not None:
        r2 = apply_op(a, r1, op1)
        if r2 is not None:
            r3 = apply_op(r2, d, op3)
            if r3 is not None:
                results.append(r3)

    # 3. (a b) (c d)
    r1 = apply_op(a, b, op1)
    r2 = apply_op(c, d, op3)
    if r1 is not None and r2 is not None:
        r3 = apply_op(r1, r2, op2)
        if r3 is not None:
            results.append(r3)

    # 4. a ((b c) d)
    r1 = apply_op(b, c, op2)
    if r1 is not None:
        r2 = apply_op(r1, d, op3)
        if r2 is not None:
            r3 = apply_op(a, r2, op1)
            if r3 is not None:
                results.append(r3)

    # 5. a (b (c d))
    r1 = apply_op(c, d, op3)
    if r1 is not None:
        r2 = apply_op(b, r1, op2)
        if r2 is not None:
            r3 = apply_op(a, r2, op1)
            if r3 is not None:
                results.append(r3)

    return results

best_run = 0
best_digits = None

ops_list = ['+', '-', '*', '/']

# Try every 4-digit set
for digits in combinations(range(10), 4):

    reachable = set()

    # All orderings of the digits
    for nums in permutations(digits):

        # All operator choices
        for ops in product(ops_list, repeat=3):

            # Evaluate all expression forms
            for val in generate_values(nums, ops):

                # Keep positive integers only
                if val.denominator == 1 and val > 0:
                    reachable.add(int(val))

    # Find longest consecutive run from 1
    n = 1
    while n in reachable:
        n += 1

    run_length = n - 1

    if run_length > best_run:
        best_run = run_length
        best_digits = digits

# Convert tuple to required string
answer = ''.join(map(str, best_digits))

print(answer)

---

Code walkthrough

Imports

from itertools import combinations, permutations, product
from fractions import Fraction

• combinations generates digit sets.
• permutations tries all digit orders.
• product generates operator triples.
• Fraction ensures exact arithmetic.

---

Operation function

def apply_op(x, y, op):

Applies one arithmetic operation.

Important detail:

if op == '/' and y == 0:
    return None

prevents division by zero.

---

Expression generation

generate_values(nums, ops)

Evaluates all 5 valid parenthesization patterns.

Example pattern:

((a b) c) d

means:

r1 = apply_op(a, b, op1)
r2 = apply_op(r1, c, op2)
r3 = apply_op(r2, d, op3)

Each successful evaluation is appended to results.

---

Main search loop

for digits in combinations(range(10), 4):

tries every 4-digit subset.

There are:

$$\binom{10}{4} = 210$$

such sets.

---

Generating all expressions

For each digit set:

for nums in permutations(digits):

tries all 24 orderings.

Then:

for ops in product(ops_list, repeat=3):

tries all 64 operator choices.

Then evaluates all 5 parenthesizations.

Total expressions per set:

$$24 \times 64 \times 5 = 7680$$

Very manageable computationally.

---

Recording integers

if val.denominator == 1 and val > 0:

keeps only positive integers.

---

Consecutive run detection

n = 1
while n in reachable:
    n += 1

finds the first missing positive integer.

Thus the run length is:

n - 1

---

Verification with the example

For the set:

$${1,2,3,4}$$

the program finds:

• all integers from $1$ through $28$,
• but not $29$,

so the run length is $28$, matching the problem statement.

---

Final verification

The known optimal set should:

• use four distinct digits,
• produce a surprisingly long consecutive sequence,
• be returned in increasing order as a 4-digit string.

The exhaustive search guarantees correctness because:

• every digit ordering is tested,
• every operator combination is tested,
• every valid parenthesization is tested,
• arithmetic is exact.

The optimal digit set is:

$${1,2,5,8}$$

which produces consecutive integers from $1$ to $51$.

Therefore the required string is:

$$1258$$

Answer: 1258