login
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.
0
1, 4, 31, 305, 3345, 39505, 487935, 6245118
OFFSET
1,2
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
EXAMPLE
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.
PROG
(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))
CROSSREFS
Sequence in context: A199683 A375434 A114475 * A349739 A359621 A076280
KEYWORD
nonn,base,uned,obsc,more
AUTHOR
David Lyness, Jun 03 2014
STATUS
approved