Project Euler

Arithmetic Expressions

Choose four distinct digits {a,b,c,d}subset{1,2,...,9}, a<b<c<d. Using each digit exactly once, together with the operations +,-,x,/ and arbitrary parentheses, we obtain a set of values. We seek th...

Source sync Apr 19, 2026

Problem #0093

Level Level 04

Solved By 13,831

Languages C++, Python

Answer 1258

Length 417 words

linear_algebrarecursionsearch

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 < b < c < d$, for which the longest set of consecutive positive integers, $1$ to $n$, can be obtained, giving your answer as a string: abcd.

Problem 93: Arithmetic Expressions

Exact search with rational arithmetic

The important observation is that every valid expression can be evaluated exactly in $\mathbb{Q}$ , so there is no need for floating-point arithmetic.

Let $R(S)$ denote the set of all rational numbers obtainable from a multiset $S$ of rational values by combining its elements with the four binary operations, using every element exactly once.

Recursive characterization

If $|S|=1$ , then $R(S)=S$ .

If $|S|\ge 2$ , choose two distinct elements $x,y\in S$ , remove them, and replace them by one of

x+y,\quad x-y,\quad y-x,\quad x y,\quad x/y\ (y\ne 0),\quad y/x\ (x\ne 0).

Then recurse on the smaller multiset.

This recursion is complete:

Every recursive contraction corresponds to a fully parenthesized expression.
Conversely, every full binary expression tree has a lowest internal node whose two children are leaves. Evaluating that node first contracts two operands into one value, reducing the problem size by one. Repeating this gives exactly a recursive contraction sequence.

Hence the recursive search generates every possible expression value, with exact rational arithmetic.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

For a multiset of size $m$ , there are at most

\binom{m}{2}

choices of unordered pair, and for each pair at most $6$ resulting values to recurse on. Therefore the number of terminal branches for one digit set is bounded by

6\binom{4}{2}\cdot 6\binom{3}{2}\cdot 6\binom{2}{2} = 36\cdot 18\cdot 6 = 3888.

There are

\binom{9}{4}=126

digit sets, so the total search is tiny.

Editorial

The search is small enough to do exhaustively, but the important implementation choice is to work with exact rational numbers. That removes all floating-point ambiguity, so every candidate value can be tested for being a positive integer with no tolerance issues.

For a fixed digit set, we recursively collapse the current multiset of values: choose two values, combine them with every legal binary operation, and continue until only one number remains. That generates every parenthesized expression. After collecting all reachable exact values, we keep only the positive integers and measure the longest consecutive prefix starting from $1$ . Repeating this over all $\binom{9}{4}$ digit sets lets us choose the best set.

Pseudocode

Set the best run length to 0 and the best digit set to empty.

For each 4-digit subset of $\{1,\dots,9\}$:
    View the four digits as exact rational numbers
    Recursively generate every reachable value by repeatedly:
        choosing two current values
        replacing them with each legal result of $+,-,\times,\div$

    Keep only the reachable values that are positive integers
    Compute the longest consecutive run starting at 1

    If this run is better than the current best:
        record the new run length and the corresponding digit set

Return the concatenation of the best four digits.

Answer

\boxed{1258}

C++ project_euler/problem_093/solution.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

struct Rational {
    long long num;
    long long den;

    Rational(long long numerator = 0, long long denominator = 1) : num(numerator), den(denominator) {
        normalize();
    }

    void normalize() {
        if (den < 0) {
            num = -num;
            den = -den;
        }
        const long long g = std::gcd(num >= 0 ? num : -num, den);
        if (g != 0) {
            num /= g;
            den /= g;
        }
    }
};

bool operator<(const Rational& a, const Rational& b) {
    return static_cast<__int128>(a.num) * b.den < static_cast<__int128>(b.num) * a.den;
}

bool operator==(const Rational& a, const Rational& b) {
    return a.num == b.num && a.den == b.den;
}

Rational operator+(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den + b.num * a.den, a.den * b.den);
}

Rational operator-(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den - b.num * a.den, a.den * b.den);
}

Rational operator*(const Rational& a, const Rational& b) {
    return Rational(a.num * b.num, a.den * b.den);
}

Rational operator/(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den, a.den * b.num);
}

std::vector<Rational> next_values(const Rational& a, const Rational& b) {
    std::vector<Rational> out = {a + b, a - b, b - a, a * b};
    if (b.num != 0) {
        out.push_back(a / b);
    }
    if (a.num != 0) {
        out.push_back(b / a);
    }
    return out;
}

void collect_values(const std::vector<Rational>& values, std::set<Rational>& out) {
    if (values.size() == 1) {
        out.insert(values[0]);
        return;
    }

    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        for (int j = i + 1; j < static_cast<int>(values.size()); ++j) {
            const Rational& a = values[i];
            const Rational& b = values[j];

            std::vector<Rational> rest;
            rest.reserve(values.size() - 1);
            for (int k = 0; k < static_cast<int>(values.size()); ++k) {
                if (k != i && k != j) {
                    rest.push_back(values[k]);
                }
            }

            for (const Rational& value : next_values(a, b)) {
                rest.push_back(value);
                collect_values(rest, out);
                rest.pop_back();
            }
        }
    }
}

std::string solve() {
    int best_len = 0;
    std::string best_digits;

    for (int a = 1; a <= 6; ++a) {
        for (int b = a + 1; b <= 7; ++b) {
            for (int c = b + 1; c <= 8; ++c) {
                for (int d = c + 1; d <= 9; ++d) {
                    std::set<Rational> reachable;
                    collect_values({Rational(a), Rational(b), Rational(c), Rational(d)}, reachable);

                    std::set<int> integers;
                    for (const Rational& value : reachable) {
                        if (value.den == 1 && value.num > 0) {
                            integers.insert(static_cast<int>(value.num));
                        }
                    }

                    int len = 0;
                    while (integers.count(len + 1) != 0) {
                        ++len;
                    }

                    if (len > best_len) {
                        best_len = len;
                        best_digits = std::to_string(a) + std::to_string(b)
                                    + std::to_string(c) + std::to_string(d);
                    }
                }
            }
        }
    }

    return best_digits;
}

int main() {
    const std::string answer = solve();
    assert(answer == "1258");
    std::cout << answer << '\n';
    return 0;
}

Python project_euler/problem_093/solution.py

"""
Project Euler Problem 93: Arithmetic Expressions

Find the set of four digits {a,b,c,d} (from {1,...,9}) for which the longest
consecutive run of positive integers 1..n can be obtained using +,-,*,/ and
parentheses, with each digit used exactly once.
"""

from fractions import Fraction
from functools import lru_cache
from itertools import combinations


def next_values(a, b):
    values = {a + b, a - b, b - a, a * b}
    if b != 0:
        values.add(a / b)
    if a != 0:
        values.add(b / a)
    return values


@lru_cache(maxsize=None)
def reachable_values(state):
    if len(state) == 1:
        return frozenset(state)

    values = list(state)
    results = set()

    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            a = values[i]
            b = values[j]
            rest = [values[k] for k in range(len(values)) if k not in (i, j)]

            for value in next_values(a, b):
                next_state = tuple(sorted(rest + [value]))
                results.update(reachable_values(next_state))

    return frozenset(results)


def solve():
    best_n = 0
    best_digits = None

    for digits in combinations(range(1, 10), 4):
        state = tuple(Fraction(digit) for digit in digits)
        reachable = reachable_values(state)
        integers = {
            value.numerator
            for value in reachable
            if value.denominator == 1 and value.numerator > 0
        }

        n = 0
        while (n + 1) in integers:
            n += 1

        if n > best_n:
            best_n = n
            best_digits = digits

    return ''.join(map(str, best_digits))


if __name__ == "__main__":
    answer = solve()
    assert answer == "1258"
    print(answer)