In their downtime, math olympiads will often play games like the following:

Given the starting integers 1, 2, 3, 4, 5, and 6 and the binary operations of addition, subtraction, multiplication, division, and exponentiation, create a mathematical expression that evaluates to the integer n, whose value is between 1 and 1000. All starting integers must be used in the expression.

Stop! Take a second to choose an n, think about the problem, and come up with a solution before reading further!

Solution

As a programmer, I didn't want to manually search for the correct mathematical expression for every n. Instead, it made more sense to create the full set of mathematical expressions possible using those starting integers and to then evaluate each one. Since the value of n was limited to only 1000 distinct values, I could then create a mapping from the values of n to the appropriate mathematical expression.

As a stepping stone to the solution, I treated the starting set of integers as a single 6-tuple that could be reduced to many different 5-tuples by applying a mathematical operation between all combinations of two numbers in the tuple. Then, I took all the newly-formed 5-tuples and repeated the process on each one to generate all the possible 4-tuples. This continued until all that was left was various 1-tuples that represented the full set of evaluated expressions.

Here's what that program looked like:

import itertools


def condense_fully(input_set):
    """Condense all n-tuples in the input set to integers."""
    results = input_set
    while not is_fully_condensed(results): 
        next_results = set()
        for input_tuple in results:
            next_results.update(condense(input_tuple))
        results = next_results
    return [x[0] for x in results]


def is_fully_condensed(input_set):
    """Determine if the input set of tuples can be further condensed."""
    return len(input_set) == 0 or len(tuple(input_set)[0]) == 1

 
def condense(input_tuple):
    """Calculate all (n-1)-tuples created after applying a binary operation
    between all combinations of two elements in the input n-tuple."""
    if len(input_tuple) < 2:
        return ()

    results = set()
    for permutation in itertools.permutations(input_tuple):
        x, y = permutation[-2:]
        for z in operate(x, y):
            result = tuple(sorted(permutation[:-2] + (z,)))
            results.add(result) 
    return results


def operate(x, y):
    """Generate the result of all binary operations between two inputs."""
    yield x + y
    yield x * y
    yield x - y
    yield y - x
    if x != 0 and y % x == 0:
        yield y//x
    if y != 0 and x % y == 0:
        yield x//y
    if 0 <= y <= 20:  # <20 limit done for performance  
        yield x**y
    if 0 <= x <= 20:  # <20 limit done for performance
        yield y**x


if __name__ == "__main__":
    start_set = {(1,2,3,4,5,6)}
    results = condense_fully(start_set) 
    results = [x for x in results if 0 < x <= 1000]
    print(sorted(results))

After doing this, I learned two things. First, performance was significantly impacted by large exponents. To reduce how long the program took to run, I limited exponents to positive integers that were less than 20. Second, the program did not find any mathematical expression that evaluated to 926. I still don't know if such an expression exists or if I have a bug.

Once I'd confirmed that I was correctly calculating all desired values for n (except 926), my next step was to tweak the program to also print out the mathematical expression used. My modifications here aren't pretty, so I'm not ready to post that version of the program yet. I'll update this post when I'm happy with that code.

Update: Here's the modified program:

import itertools
from collections import namedtuple


Expression = namedtuple("Expression", ["value", "formula"])


def condense_fully(input_set):
    """Condense all n-tuples in the input set to integers."""
    results = input_set
    while not is_fully_condensed(results): 
        next_results = {}
        for input_tuple in results:
            for next_result in condense(input_tuple):
                result_id = tuple(x.value for x in next_result)
                if result_id not in next_results:
                    next_results[result_id] = next_result
        results = next_results.values()
    return [x[0] for x in results]


def is_fully_condensed(input_set):
    """Determine if the input set of tuples can be further condensed."""
    return len(input_set) == 0 or len(tuple(input_set)[0]) == 1

 
def condense(input_tuple):
    """Calculate all (n-1)-tuples created after applying a binary operation
    between all combinations of two elements in the input n-tuple."""
    if len(input_tuple) < 2:
        return ()

    else:
        results = set()
        for permutation in itertools.permutations(input_tuple):
            x, y = permutation[-2:]
            for z in operate(x, y):
                result = tuple(sorted(permutation[:-2] + (z,)))
                results.add(result)
    return results


def operate(expr1, expr2):
    """Generate the result of all binary operations between two inputs."""
    x1, y1 = expr1.value, expr2.value
    x2, y2 = expr1.formula, expr2.formula
    yield Expression(x1 + y1, f"({x2}+{y2})")
    yield Expression(x1 * y1, f"({x2}*{y2})")
    yield Expression(x1 - y1, f"({x2}-{y2})")
    yield Expression(y1 - x1, f"({y2}-{x2})")
    if x1 != 0 and y1 % x1 == 0:
        yield Expression(y1//x1, f"({y2}/{x2})")
    if y1 != 0 and x1 % y1 == 0:
        yield Expression(x1//y1, f"({x2}/{y2})")
    if 0 <= y1 <= 20:
        yield Expression(x1**y1, f"({x2}**{y2})")
    if 0 <= x1 <= 20:
        yield Expression(y1**x1, f"({y2}**{x2})")


if __name__ == "__main__":
    start_set = {tuple(Expression(x+1, f"{x+1}") for x in range(6))}
    results = condense_fully(start_set) 
    results = [x for x in results if 0 <= x.value <= 1000]
    print(sorted(results))

I'm still hung up on one thing though. Does anyone know how to produce the mathematical expression that evaluates to 926?