Problem 259: Reachable Numbers

Project Euler Problem 259 Solution

EulerSolve provides an optimized solution for Project Euler Problem 259, Reachable Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A positive integer is called reachable if it can be obtained from the digits 1,2,3,4,5,6,7,8,9 used in this exact order and exactly once each, under the following rules: 1. Between two consecutive digits we may place one of the four binary operations + , - , * , / , or we may concatenate the digits. 2. Parentheses may be inserted arbitrarily. 3. Unary minus is not allowed. The goal is to find the sum of all distinct positive integers that are reachable exactly. Mathematical Approach 1. Encoding Every Admissible Expression There are 8 gaps between the 9 digits. In each gap we choose one symbol from $$\{+,-,\times,\div,\#\},$$ where $\#$ means decimal concatenation. Therefore the total number of raw operator patterns is $$5^8=390625.$$ For example, the pattern 1#2 + 3#4 * 5 - 6#7#8 / 9 collapses to the token list $$12,\ 34,\ 5,\ 678,\ 9$$ with operator list $$+,\ \times,\ -,\ \div.$$ So after concatenations are resolved, every pattern becomes a sequence $$v_0,v_1,\dots,v_{m-1}\in \mathbb Z_{>0}$$ together with operators $$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$ where $1\le m\le 9$. 2. Why Parentheses Lead to Interval Dynamic Programming Once the token list is fixed, the only remaining freedom is the parenthesization....

Detailed mathematical approach

Problem Summary

An expression is built from the digits $1$ to $9$, each used exactly once and in this order. Neighbouring digits may be joined into one number, as $2$, $3$ and $4$ give $234$; the numbers are combined by addition, subtraction, multiplication and division, each as often as we like; nested parentheses may fix the order of the operations; and a unary minus, a minus sign in front of a single operand, is not allowed. A positive integer is reachable if some such expression has it as its value; for example, $(1/23)\times((4\times5)-6)$${}\times(78-9)=42$. We must find the sum of all positive reachable integers, each counted once. ^[1]

The whole solution in one sentence: an expression is fixed by what stands in each of the eight gaps between neighbouring digits, nothing or one of the four operations, and by its parentheses, so we run through all $5^8=390625$ choices for the gaps, find the values of all placements of parentheses by combining, as exact fractions, the values on the two sides of the last operation, and add up the distinct positive integers among the results.

Mathematical Approach

We start with three digits, separate the gaps from the parentheses, handle the parentheses with one recursion and explain why the values must be exact fractions.

1. Three digits by hand

Take only the digits $1,2,3$. Writing nothing in both gaps gives $123$. Joining one pair gives $12\circ3$ or $1\circ23$, where $\circ$ is one of the four operations, with the values $15,9,36,4$ and $24,-22,23,1/23$. An operation in both gaps gives $16$ rows such as $1-2\times3$, each with two placements of parentheses, here $(1-2)\times3=-3$ and $1-(2\times3)=-5$. These $1+8+32=41$ expressions take $28$ different values, and $12$ of them are positive integers: $1=(1+2)/3$, $2=1-(2-3)$, $4=12/3$, $5=1\times(2+3)$, $6$, $7$, $9$, $15$, $23$, $24$, $36$ and $123$, with the sum $255$. Negative values may occur inside, as in $1-(2-3)$; only a minus sign without a left operand is forbidden. And only digits may be joined: the value of $1+2$ cannot be joined with $3$ to give $33$.

With these three digits the number $3$ is not reachable, and the reason contains the key idea. Every expression other than $123$ has a last operation, which splits the digits as $1\,2\mid3$ or as $1\mid2\,3$. The expressions on $1,2$ have the values $12,3,-1,2,1/2$, and those on $2,3$ the values $23,5,-1,6,2/3$. Now $a\circ3=3$ would need $a=0$, $6$, $1$ or $9$ for $\circ=+,-,\times,\div$, and $1\circ b=3$ would need $b=2$, $-2$, $3$ or $1/3$; none of these occurs. What a row can produce depends only on the sets of values of the two sides of the last operation.

2. Gaps and blocks

Each of the eight gaps receives one of five symbols: nothing, which joins its two digits, or one of $+,-,\times,\div$. The gaps that carry an operation cut the digits into blocks of consecutive digits, in one of $2^8=256$ ways, and a cutting into $m$ blocks has $m-1$ such gaps, each with one of four operations. Altogether there are $5^8=390625$ gap codes. The example of the statement has the code $\div$, nothing, $\times$, $\times$, $-$, $\times$, nothing, $-$, with the blocks $1,23,4,5,6,78,9$ and the operations $\div,\times,\times,-,\times,-$. For one code we write the blocks as numbers $v_0,\dots,v_{m-1}$ and the operations as $o_0,\dots,o_{m-2}$, with $o_k$ between $v_k$ and $v_{k+1}$.

3. Parentheses are binary trees

A complete placement of parentheses on the row $v_0\,o_0\,v_1\cdots o_{m-2}\,v_{m-1}$ is a binary tree: its leaves are the numbers in their order, and each inner node applies an operation to the values of its two subtrees. The node whose subtrees hold $v_l,\dots,v_k$ and $v_{k+1},\dots,v_r$ is the operation in the gap between $v_k$ and $v_{k+1}$, that is $o_k$. The number of such trees is the Catalan number ^[2]

$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1},$$

which is $1,1,2,5,14,42,132,429,1430$ for $m=1,\dots,9$. With $k+1$ blocks there are $\binom8k$ cuttings, $4^k$ choices of operations and $C_k$ trees, so there are

$$\sum_{k=0}^{8}\binom{8}{k}4^kC_k=167\,763\,361$$

expressions, some of which divide by $0$. Evaluating them one by one would take up to $1\,247\,275\,296$ arithmetic operations, $k$ per tree, although the trees share large subtrees.

4. The last operation

For one gap code, let $R_{l,r}$ be the set of values of all placements of parentheses on the part $v_l\,o_l\cdots o_{r-1}\,v_r$ of the row. For sets $A$, $B$ and an operation $o$, let $A\,o\,B$ be the set of all $a\,o\,b$ with $a\in A$ and $b\in B$, leaving out $b=0$ when $o$ is $\div$. Then $R_{l,l}=\{v_l\}$, and for $l\lt r$

$$R_{l,r}=\bigcup_{k=l}^{r-1}R_{l,k}\;o_k\;R_{k+1,r}.$$

The proof is an induction on $r-l$. A tree on $v_l,\dots,v_r$ with $r\gt l$ has a root, its last operation, which is $o_k$ for some $k$ with $l\le k\lt r$. Its two subtrees are trees on $v_l,\dots,v_k$ and on $v_{k+1},\dots,v_r$, so its value is $a\,o_k\,b$ with $a\in R_{l,k}$ and $b\in R_{k+1,r}$. Conversely, two trees with the values $a$ and $b$, joined by $o_k$, form a tree on $v_l,\dots,v_r$ with the value $a\,o_k\,b$, as long as we do not divide by $0$. Computing the sets for the parts of length $1,2,\dots,m$, each part once, is the dynamic programming over contiguous parts known from matrix chain multiplication. ^[3]

5. Worked example: $17$ from four digits

Give the digits $1,2,3,4$ the gaps $\div$, $\times$, nothing. The row is $1\div2\times34$, so $v_0=1$, $v_1=2$ and $v_2=34$, and the recursion gives:

$R_{0,0}=\{1\}$, $R_{1,1}=\{2\}$ and $R_{2,2}=\{34\}$;
$R_{0,1}=\{1/2\}$ and $R_{1,2}=\{68\}$;
for $R_{0,2}$, the split after $v_0$ gives $1\div68=1/68$, and the split after $v_1$ gives $(1/2)\times34=17$, so $R_{0,2}=\{1/68,17\}$.

So the digits $1$ to $4$ can make $17$, and the gaps $\div$, $\div$, nothing give it again as $1/(2/34)$; these are the only two expressions for $17$, and both pass through a fraction. The $429$ expressions on four digits take $163$ values; of the $44$ positive integers among them, with the sum $4179$, $17$ is the only one that needs a fraction.

6. The example of the statement

For the row $1\div23\times4\times5-6\times78-9$ of Section 2, the recursion finds $R_{0,1}=\{1/23\}$, $R_{5,6}=\{69\}$ and $R_{2,4}=\{14,-4\}$, from $(4\times5)-6$ and $4\times(5-6)$. The split at $o_1=\times$ puts $(1/23)\times14=14/23$ into $R_{0,4}$, and the split at $o_4=\times$ puts $(14/23)\times69=42$ into $R_{0,6}$. Equal values are stored once: this row has $C_6=132$ trees but only $69$ different values, and just two of them are positive integers, $42$ and

$$1=1/\bigl(23\times4\times5-(6\times78-9)\bigr).$$

7. Exact fractions

Every rational number has exactly one form $p/q$ with $q\gt0$ and $\gcd(p,q)=1$, reached by dividing numerator and denominator by their greatest common divisor and, if needed, changing both signs. ^[4] With $x=a/b$ and $y=c/d$, the operations give

$$\begin{aligned}x\pm y&=\frac{ad\pm bc}{bd},\\ xy&=\frac{ac}{bd},\qquad \frac{x}{y}=\frac{ad}{bc},\end{aligned}$$

and reducing the result restores the form. So two values are equal exactly when their pairs $(p,q)$ are equal, and a value is a positive integer exactly when $q=1$ and $p\gt0$. The value $0$ and negative values are kept for later operations; only a division by a part with the value $0$, such as $2-3-4+5$, is skipped.

Integers alone would not suffice: $1935$ reachable integers can only be obtained through a value that is not an integer, the smallest being

$$\begin{aligned}6538&=12\times\bigl((3+4)\\&\qquad{}\times(5/(6/7)+8\times9)\bigr),\end{aligned}$$

where $5/(6/7)=35/6$. Floating-point numbers would not suffice either: $6/7$ has no finite binary expansion and is rounded, ^[5] and evaluated in double precision in the order written, this expression gives $6537.999999999999$. A test for an exact integer misses $6538$ here, and a tolerance would need an error analysis of its own.

8. How large the numbers get

Let the height of a reduced fraction $p/q$ be $H=\max(|p|,q)$. The formulas of Section 7 give $H(x\pm y)\le2H(x)H(y)$, $H(xy)\le H(x)H(y)$ and $H(x/y)\le H(x)H(y)$, since reducing only makes the numbers smaller. By induction over the tree, every value on a row with the numbers $t_1,\dots,t_m$ has a height of at most $2^{m-1}t_1\cdots t_m$, and the bound for a part of the row is no larger, as all numbers are at least $1$. Over the $256$ cuttings of Section 2 the largest bound belongs to the blocks $12345,6,7,8,9$, and it is below $2^{31}$:

$$2^4\cdot12345\cdot6\cdot7\cdot8\cdot9=597\,300\,480.$$

The true values are smaller still: over all expressions on all runs of consecutive digits, the largest numerator in absolute value is $123\,456\,789$, and the largest denominator is $23\,456\,789$, from $1/23456789$. Since $|p/q|\le|p|$, the largest reachable integer is $123456789$ itself; the only others above $10^8$ are $12345678\times9=111111102$ and $1234567\times89=109876463$.

9. Collecting the reachable integers

The same integer appears for many gap codes: the $390625$ codes give $3\,505\,210$ pairs of a code and a positive integer in its set $R_{0,m-1}$, but only $72585$ different positive integers. They are gathered in one set and added once each; the sum is below $72585\cdot123456789\lt10^{13}$, so a 64-bit integer holds it. Every integer from $1$ to $6963$ is reachable, and the smallest unreachable ones are $6964$, $7666$, $7834$ and $7978$.

10. A shorter route over digit runs

The per-code method repeats work: a part of a row depends only on its own gaps, yet it is computed again for every choice of the other gaps. As in Section 1, let $D_{i,j}$ be the set of values of all expressions on the digits $i,\dots,j$; by the proof of Section 4 it consists of the number written by these digits and all $a\circ b$ with $i\le k\lt j$, $a\in D_{i,k}$, $b\in D_{k+1,j}$ and $\circ$ any of the four operations, again without division by $0$. The full run then has $3\,244\,635$ values, $136\,607$ of them integers, and the computation forms $15\,424\,428$ results, about twelve times fewer than the $180\,712\,942$ of the per-code method. Computer searches for the four fours puzzle work in the same way. ^[6]

How the Code Works

The C++ program ^[7] implements Sections 2 to 9. Gap codes run from $0$ to $5^8-1$, with the bound kTotalExpressions; their base-5 digits, lowest first, are the symbols of the gaps after the digits $1,\dots,8$, and op_from_code maps $0,1,2,3$ to $+,-,\times,\div$ and $4$ to the joining marker #. collect_for_range decodes each code into the vectors values and ops, joining digits as current * 10 + next_digit. all_results(values, ops) runs Section 4 on a table dp of vectors, parts in order of increasing length: for each split $k$ it combines every pair from dp[l][k] and dp[k+1][r] by apply with ops[k], skipping divisions by $0$ before apply could throw, and keeps each new value once with the std::set named seen.

The values are boost::rational<std::int64_t>, always reduced with a positive denominator, ^[8] so the test of Section 7 is denominator() == 1 and numerator() > 0, and by Section 8 the 64-bit integers never come near an overflow. The positive integers of a range are sorted and freed of repetitions at its end. main cuts the codes into consecutive ranges of nearly equal length, joins their results, removes repetitions again, adds the integers in a cpp_int and prints the count, the sum, and the sum again after Answer:.

The Java program decodes the codes in solve, with choice == 4 as the joining symbol. It packs a reduced fraction into one long, the numerator in the upper and the denominator in the lower 32 bits (makeFrac, num, den), and applyOp returns INVALID, which is Long.MIN_VALUE, for a division by zero. The packing is faithful for $-2^{31}\le p\lt2^{31}$ and $0\lt q\lt2^{32}$; Section 8 guarantees heights of at most $597\,300\,480$, and the unreduced products in applyOp stay below $2\cdot597\,300\,480^2\lt2^{63}$. allResults keeps the values of each part in a HashSet<Long> and returns only the positive integers of the whole row, which solve unites in the set allPos and adds in a long.

The Python file is a bridge: solve compiles solutionsCpp/Euler259.cpp with clang++ or g++ (-std=c++17 -O2) into the hidden file .euler259_py_bridge when that file is missing or older than the source, runs it, and parse_output returns the text after the last Answer:. It raises an error when no compiler is found, when the compilation or the run fails, or when the program prints nothing. No include path is passed, so the compiler must find the Boost headers by itself.

Complexity and Verification

Over all $390625$ codes the per-code method tries $180\,817\,780$ pairs of values and skips $104\,838$ divisions by zero. Every other pair costs one fraction operation with a reduction and one set lookup, logarithmic in the size of the set for the std::set of C++ and constant on average for the hash sets of Java. Counted in such combinations, this is about a seventh of evaluating every tree separately and about twelve times the work of Section 10. The largest set, $1219$ values from $1430$ trees, belongs to $1-2\div3-4\div5-6\div7+8\times9$, whose table holds $2612$ fractions, the most for any code. Besides that table, the C++ program stores the integers of a range with repetitions until it sorts them, $3\,505\,210$ over all ranges, and the Java program stores each integer once. On an Apple M4 Max the C++ program takes about $2$ seconds and the Java program about $11$ seconds; the Python bridge compiles only when its cached executable is missing or older than the source.

The programs contain no self-tests or comparisons with known values. For this article we verified that the three programs print the same sum; that a separate program for Section 10, with its own fraction type and 128-bit products, finds the same $72585$ integers and sum, the extreme values of Sections 8 and 9, and $70650$ integers when all intermediate values must be integers; that a separate copy of the per-code method reproduces the counts above; and that brute force over all trees for three and four digits and over the $132$ trees of the row of Section 6 confirms Sections 1, 5 and 6. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above; the recursion, the worked examples, the height bound and all counts are derived or computed in this article.

Project Euler 259 — Reachable Numbers. The official statement allows the digits 1 to 9 in order, each once, concatenation of successive digits, the four basic operations and nested parentheses, but no unary minus; it gives the example for 42 and asks for the sum of all positive reachable integers.
Wikipedia — Catalan number. Cₙ = C(2n, n)/(n + 1) counts the complete parenthesisations of n + 1 factors and the full binary trees with n + 1 leaves: 1, 1, 2, 5, 14, 42, 132, 429, 1430, …
Wikipedia — Matrix chain multiplication. The dynamic programming solution splits a chain into two contiguous parts at every position and saves the result for each part, so that it is computed only once.
Wikipedia — Rational number. Every rational number is a unique irreducible fraction a/b with b > 0, found by dividing by the greatest common divisor; the article gives the formulas for sum, product and quotient.
Wikipedia — Floating-point arithmetic. A number such as 1/3 has no exact binary representation, results are rounded, and testing for equality is problematic.
Wikipedia — Four fours. Expressions of whole numbers with four 4s are found there by building hash tables of rational values for more and more 4s from pairs of smaller subexpressions, computing each table once.
C++ — Euler259.cpp. This immutable revision is the implementation record for this article; the copy on this site only adds the final output line starting with Answer:, which the Python bridge reads.
Boost.Rational documentation. Values are held in normalised form, without common factors and with a positive denominator; with a fixed-width integer type, an overflow makes the results undefined.

Problem 259 source code

C++

#include <boost/rational.hpp>

#include <cstdint>
#include <iostream>
#include <set>
#include <vector>
#include <thread>
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>

using i64 = std::int64_t;
using Fraction = boost::rational<i64>;
using cpp_int = boost::multiprecision::cpp_int;

namespace {

const std::string kDigits = "123456789";
constexpr int kTotalSplits = 8;
constexpr int kOperatorCount = 5;
constexpr int kOperators = kOperatorCount;
constexpr int kTotalExpressions = 390625;  // 5^8

char op_from_code(int code) {
    if (code == 0) return '+';
    if (code == 1) return '-';
    if (code == 2) return '*';
    if (code == 3) return '/';
    return '#'; // concat marker
}

Fraction apply(Fraction lhs, const Fraction& rhs, char op) {
    switch (op) {
        case '+':
            return lhs + rhs;
        case '-':
            return lhs - rhs;
        case '*':
            return lhs * rhs;
        case '/':
            if (rhs == 0) {
                throw std::overflow_error("division by zero");
            }
            return lhs / rhs;
    }
    return lhs;
}

std::vector<Fraction> all_results(const std::vector<i64>& values, const std::vector<char>& ops) {
    const int n = static_cast<int>(values.size());
    std::vector<std::vector<std::vector<Fraction>>> dp(static_cast<size_t>(n),
                                                      std::vector<std::vector<Fraction>>(static_cast<size_t>(n)));

    for (int i = 0; i < n; ++i) {
        dp[static_cast<size_t>(i)][static_cast<size_t>(i)] = {Fraction(values[static_cast<size_t>(i)], 1)};
    }

    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            const int r = l + len - 1;
            std::set<Fraction> seen;
            std::vector<Fraction> combined;

            for (int k = l; k < r; ++k) {
                const auto& left = dp[static_cast<size_t>(l)][static_cast<size_t>(k)];
                const auto& right = dp[static_cast<size_t>(k + 1)][static_cast<size_t>(r)];
                const char op = ops[static_cast<size_t>(k)];

                for (const Fraction& a : left) {
                    for (const Fraction& b : right) {
                        if (op == '/' && b == 0) {
                            continue;
                        }
                        Fraction v = apply(a, b, op);
                        if (seen.insert(v).second) {
                            combined.push_back(v);
                        }
                    }
                }
            }
            dp[static_cast<size_t>(l)][static_cast<size_t>(r)] = std::move(combined);
        }
    }

    return dp[0][static_cast<size_t>(n - 1)];
}

void collect_for_range(int start, int end, std::vector<i64>& out) {
    for (int code = start; code < end; ++code) {
        int x = code;
        std::vector<i64> values;
        values.reserve(9);
        std::vector<char> ops;
        ops.reserve(8);

        i64 current = kDigits[0] - '0';
        for (std::size_t i = 0; i < kDigits.size() - 1; ++i) {
            const int choice = x % kOperators;
            x /= kOperators;
            const i64 next_digit = static_cast<i64>(kDigits[i + 1] - '0');

            const char op = op_from_code(choice);
            if (op == '#') {
                current = current * 10 + next_digit;
            } else {
                values.push_back(current);
                ops.push_back(op);
                current = next_digit;
            }
        }
        values.push_back(current);

        const auto results = all_results(values, ops);
        for (const Fraction& v : results) {
            if (v.denominator() == 1 && v.numerator() > 0) {
                out.push_back(v.numerator());
            }
        }
    }

    std::sort(out.begin(), out.end());
    out.erase(std::unique(out.begin(), out.end()), out.end());
}

}  // namespace

int main() {
    const unsigned threads = std::max(1u, std::thread::hardware_concurrency());
    const int base = kTotalExpressions / static_cast<int>(threads);
    const int rem = kTotalExpressions % static_cast<int>(threads);

    std::vector<std::vector<i64>> thread_results(threads);
    std::vector<std::thread> workers;
    workers.reserve(threads);

    int start = 0;
    for (unsigned t = 0; t < threads; ++t) {
        const int extra = t < static_cast<unsigned>(rem) ? 1 : 0;
        const int end = start + base + extra;
        workers.emplace_back(collect_for_range, start, end, std::ref(thread_results[static_cast<size_t>(t)]));
        start = end;
    }

    for (auto& worker : workers) {
        worker.join();
    }

    std::vector<i64> all;
    for (const auto& vec : thread_results) {
        all.insert(all.end(), vec.begin(), vec.end());
    }
    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());

    cpp_int sum = 0;
    for (const i64 v : all) {
        sum += v;
    }

    std::cout << "Total number of unique reachable numbers: " << all.size() << '\n';
    std::cout << "Sum of all unique reachable integers: " << sum << '\n';
    std::cout << "Answer: " << sum << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""

    answer_candidates = []
    equal_candidates = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answer_candidates.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equal_candidates.append(m2.group(1).strip())

    if answer_candidates:
        return answer_candidates[-1]
    if equal_candidates:
        return equal_candidates[-1]
    return lines[-1]


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = subprocess.check_output([str(binary)], text=True)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


if __name__ == "__main__":
    print(solve())

Java

import java.util.*;

public class Euler259 {
    public static String solve() {
        int OPS = 5;
        int totalExpr = 1;
        for (int i = 0; i < 8; i++)
            totalExpr *= OPS;
        Set<Long> allPos = new HashSet<>();

        for (int code = 0; code < totalExpr; code++) {
            int x = code;
            List<Integer> values = new ArrayList<>();
            List<Integer> ops = new ArrayList<>();
            int current = 1;
            for (int i = 0; i < 8; i++) {
                int choice = x % OPS;
                x /= OPS;
                int next = i + 2;
                if (choice == 4) {
                    current = current * 10 + next;
                } else {
                    values.add(current);
                    ops.add(choice);
                    current = next;
                }
            }
            values.add(current);
            Set<Long> results = allResults(values, ops);
            for (long v : results)
                if (v > 0)
                    allPos.add(v);
        }
        long sum = 0;
        for (long v : allPos)
            sum += v;
        return String.valueOf(sum);
    }

    // Fraction: numerator in high 32, denominator in low 32 (signed)
    static final long INVALID = Long.MIN_VALUE;

    static long makeFrac(long n, long d) {
        if (d == 0)
            return INVALID;
        if (d < 0) {
            n = -n;
            d = -d;
        }
        long g = gcd(Math.abs(n), d);
        return ((n / g) << 32) | (d / g);
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static long num(long f) {
        return f >> 32;
    }

    static long den(long f) {
        return f & 0xFFFFFFFFL;
    }

    static long applyOp(long a, long b, int op) {
        long an = num(a), ad = den(a), bn = num(b), bd = den(b);
        switch (op) {
            case 0:
                return makeFrac(an * bd + bn * ad, ad * bd);
            case 1:
                return makeFrac(an * bd - bn * ad, ad * bd);
            case 2:
                return makeFrac(an * bn, ad * bd);
            case 3:
                return bn == 0 ? INVALID : makeFrac(an * bd, ad * bn);
            default:
                return INVALID;
        }
    }

    static Set<Long> allResults(List<Integer> values, List<Integer> ops) {
        int n = values.size();
        Set<Long>[][] dp = new HashSet[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = new HashSet<>();
            dp[i][i].add(makeFrac(values.get(i), 1));
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int r = l + len - 1;
                dp[l][r] = new HashSet<>();
                for (int k = l; k < r; k++) {
                    int op = ops.get(k);
                    for (long a : dp[l][k]) {
                        for (long b : dp[k + 1][r]) {
                            long v = applyOp(a, b, op);
                            if (v != INVALID)
                                dp[l][r].add(v);
                        }
                    }
                }
            }
        }
        Set<Long> result = new HashSet<>();
        for (long f : dp[0][n - 1])
            if (den(f) == 1) {
                long v = num(f);
                if (v > 0)
                    result.add(v);
            }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}