A243312 The total T(d,n) of expressions with n instances of a digit d between 6 and 9 (and using the four arithmetic operators) which have a defined value when evaluated.

1, 4, 31, 305, 3345, 39505, 487935, 6245118

Offset: 1

Author

David Lyness, Jun 03 2014

Keywords

• nonn
• base
• uned
• obsc
• more

Comments

Bounded above by A151403 (which is equal to the *total* number of expressions, not just the ones that evaluate to a valid numeric value).

An expression has an undefined value when it contains a "division by zero" operation.

For 0 <= d <= 5 and d' > 5, it is possible that T(d,n) < T(d',n). See link below.

T(6,10) = 1097128463 < T(7,10) = 1097153419 < T(8,10) = 1097155971 < T(9,10) = 1097157195. - Hiroaki Yamanouchi, Oct 01 2014

Examples

			For n = 2 and digit d != 0, there are four possible expressions:
(d + d)
(d - d)
(d * d)
(d / d)
None of these include a "division by zero" operation, and so all four of the above expressions can be considered valid. Therefore, T(d, 2) = 4 for d > 0.
		

Links

• David Lyness, Experimenting with bracketing and binary operators

Programs

Python

# coding=utf-8
 
import itertools
 
 
def all_expressions(generic_expression, operation_combinations):
    """
    Merges a source expression and combinations of binary operators to generate a list of all possible expressions.
    @param ((str,)) operation_combinations: all combinations of binary operators to consider
    @param str generic_expression: source expression with placeholder binary operators
    @rtype: (str,)
    """
    expression_combinations = []
    for combination in operation_combinations:
        expression_combinations.append(generic_expression.format(*combination))
    return expression_combinations
 
 
def all_bracketings(expr):
    """
    Generates all possible permutations of parentheses for an expression.
    @param str expr: the non-bracketed source expression
    @rtype: str
    """
    if len(expr) == 1:
        yield expr
    else:
        for i in range(1, len(expr), 2):
            for left_expr in all_bracketings(expr[:i]):
                for right_expr in all_bracketings(expr[i + 1:]):
                    yield "({}{}{})".format(left_expr, expr[i], right_expr)
 
 
def num_valid_expressions(num_digits):
    """Perform all calculations with the given operations and in the range of digits specified.
    @param int num_digits: the number of digits in the expression
    @rtype: int
    """
    operations = ["+", "-", "*", "/"]
    digit = 9
    operation_iterable = itertools.product(*[operations] * (num_digits - 1))
    operation_combinations = []
    valid_expression_count = 0
    template = " ".join(str(digit) * num_digits)
    for operation in operation_iterable:
        operation_combinations.append(operation)
    for bracketed_expression in all_bracketings(template):
        for expression in all_expressions(bracketed_expression.replace(" ", "{}"), operation_combinations):
            try:
                eval(expression)
                valid_expression_count += 1
            except ZeroDivisionError:
                pass
    return valid_expression_count
 
 
if _name_ == "_main_":
    min_num_digits = 1
    max_num_digits = 6
    operation_set = ["+", "-", "*", "/"]
    for num in range(min_num_digits, max_num_digits + 1):
        print(num_valid_expressions(num))