|
%I #22 Feb 13 2021 10:21:33
%S 1,4,31,305,3345,39505,487935,6245118
%N 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.
%C Bounded above by A151403 (which is equal to the *total* number of expressions, not just the ones that evaluate to a valid numeric value).
%C An expression has an undefined value when it contains a "division by zero" operation.
%C For 0 <= d <= 5 and d' > 5, it is possible that T(d,n) < T(d',n). See link below.
%C T(6,10) = 1097128463 < T(7,10) = 1097153419 < T(8,10) = 1097155971 < T(9,10) = 1097157195. - _Hiroaki Yamanouchi_, Oct 01 2014
%H David Lyness, <a href="https://davidlyness.com/post/experimenting-bracketing-binary-operators">Experimenting with bracketing and binary operators</a>
%e For n = 2 and digit d != 0, there are four possible expressions:
%e (d + d)
%e (d - d)
%e (d * d)
%e (d / d)
%e 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.
%o (Python)
%o # coding=utf-8
%o .
%o import itertools
%o .
%o .
%o def all_expressions(generic_expression, operation_combinations):
%o ...."""
%o ....Merges a source expression and combinations of binary operators to generate a list of all possible expressions.
%o ....@param ((str,)) operation_combinations: all combinations of binary operators to consider
%o ....@param str generic_expression: source expression with placeholder binary operators
%o ....@rtype: (str,)
%o ...."""
%o ....expression_combinations = []
%o ....for combination in operation_combinations:
%o ........expression_combinations.append(generic_expression.format(*combination))
%o ....return expression_combinations
%o .
%o .
%o def all_bracketings(expr):
%o ...."""
%o ....Generates all possible permutations of parentheses for an expression.
%o ....@param str expr: the non-bracketed source expression
%o ....@rtype: str
%o ...."""
%o ....if len(expr) == 1:
%o ........yield expr
%o ....else:
%o ........for i in range(1, len(expr), 2):
%o ............for left_expr in all_bracketings(expr[:i]):
%o ................for right_expr in all_bracketings(expr[i + 1:]):
%o ....................yield "({}{}{})".format(left_expr, expr[i], right_expr)
%o .
%o .
%o def num_valid_expressions(num_digits):
%o ...."""Perform all calculations with the given operations and in the range of digits specified.
%o ....@param int num_digits: the number of digits in the expression
%o ....@rtype: int
%o ...."""
%o ....operations = ["+", "-", "*", "/"]
%o ....digit = 9
%o ....operation_iterable = itertools.product(*[operations] * (num_digits - 1))
%o ....operation_combinations = []
%o ....valid_expression_count = 0
%o ....template = " ".join(str(digit) * num_digits)
%o ....for operation in operation_iterable:
%o ........operation_combinations.append(operation)
%o ....for bracketed_expression in all_bracketings(template):
%o ........for expression in all_expressions(bracketed_expression.replace(" ", "{}"), operation_combinations):
%o ............try:
%o ................eval(expression)
%o ................valid_expression_count += 1
%o ............except ZeroDivisionError:
%o ................pass
%o ....return valid_expression_count
%o .
%o .
%o if __name__ == "__main__":
%o ....min_num_digits = 1
%o ....max_num_digits = 6
%o ....operation_set = ["+", "-", "*", "/"]
%o ....for num in range(min_num_digits, max_num_digits + 1):
%o ........print(num_valid_expressions(num))
%K nonn,base,uned,obsc,more
%O 1,2
%A _David Lyness_, Jun 03 2014
| 