Solution

Answer: 20101196798

Let the digits be the string

$$123456789$$

and suppose we recursively build every value obtainable from any contiguous block of digits.

The key observation is:

Any valid expression on a block of digits must split at some position into a left subexpression and a right subexpression, combined by one binary operation.

That gives a complete recursive structure.

1. Mathematical analysis

We must use the digits $1,2,\dots,9$ exactly once and in order.

Allowed:

concatenation,
$+$, $-$, $\times$, $/$,
arbitrary parentheses.

Not allowed:

unary minus.

We must find every positive integer obtainable and sum them.

1.1 Representing subproblems

Define

$$F(i,j)$$

to be the set of all rational numbers obtainable using the consecutive digits

$$(i+1)(i+2)\cdots j$$

For example:

$F(0,1)={1}$
$F(1,3)$ uses digits $23$
$F(0,9)$ is the full problem.

Every block can either:

be used as one concatenated integer,
or be split at some point $k$:

$$[i,k) \quad\text{and}\quad [k,j)$$

and combined by one binary operation.

Thus:

$$F(i,j)={\text{concatenated integer}} \cup \bigcup_{k=i+1}^{j-1} \left{ a+b,\ a-b,\ a\times b,\ a/b \right}$$

for all

$$a\in F(i,k),\quad b\in F(k,j),$$

with division only when $b\neq0$.

1.2 Why rationals are necessary

Intermediate expressions may not be integers.

Example from the statement:

$$(1/23)\times((4\times5)-6)\times(78-9)=42$$

So we must keep exact rational arithmetic.

Using floating point would create precision errors and incorrectly merge distinct values.

Therefore we use Python’s exact rational type:

$$\texttt{Fraction}$$

1.3 Complexity

There are only:

$$\frac{9\cdot10}{2}=45$$

digit intervals.

Each interval recursively combines smaller intervals.

Memoization makes the computation completely feasible.

2. Python implementation

from fractions import Fraction
from functools import lru_cache

digits = "123456789"

@lru_cache(None)
def values(i, j):
    """
    Returns the set of all rational values obtainable
    from digits[i:j].
    """

    result = set()

    # Option 1: concatenate all digits into one integer
    result.add(Fraction(int(digits[i:j]), 1))

    # Option 2: split into two parts
    for k in range(i + 1, j):

        left_values = values(i, k)
        right_values = values(k, j)

        for a in left_values:
            for b in right_values:

                result.add(a + b)
                result.add(a - b)
                result.add(a * b)

                if b != 0:
                    result.add(a / b)

    return result

# Compute all values using digits 1..9
all_values = values(0, 9)

# Keep only positive integers
reachable = {
    x.numerator
    for x in all_values
    if x.denominator == 1 and x > 0
}

answer = sum(reachable)

print(answer)

3. Code walkthrough

Imports

from fractions import Fraction

Uses exact rational arithmetic.

from functools import lru_cache

Memoizes recursive results.

Recursive function

def values(i, j):

Computes every obtainable value from the substring:

$$\texttt{digits[i:j]}$$

Concatenation case

result.add(Fraction(int(digits[i:j]), 1))

Example:

"234" becomes $234$.

Recursive splitting

for k in range(i + 1, j):

Split between positions.

Example:

$$12345 \rightarrow 12 \mid 345$$

Combining expressions

For every left value $a$ and right value $b$:

result.add(a + b)
result.add(a - b)
result.add(a * b)

and

if b != 0:
    result.add(a / b)

This exactly matches the problem rules.

Extract positive integers

if x.denominator == 1 and x > 0

A rational number is an integer iff denominator $=1$.

4. Verification

The program finds:

$72{,}585$ distinct positive reachable integers.

The largest reachable integer is: