[math-fun] puzzle family: values of parenthesized expressions
Someone recently gave me a random programming problem: to find the number of unique values of an infix expression (like say 1+2-3*4) parenthesized in all possible ways (in this example it's three: {-9 -3 0} because of the five ways two produce duplicate results). The operators were restricted to {+ - *}, the operands to positive integers. Somewhat arbitrary, but a fun puzzle... Anyway, I was wondering: is there a method for constructing such expressions such that over parenthesization they give the maximum possible Catalan(N) unique values? What is the maximum achievable if the operators are restricted to {+ *} or {- *}? Perhaps there are also interesting puzzles with restrictions on the operands, such as when they are all the same value, or powers of two, or the like...
In general, Catalan(N) unique values cannot be achieved. If the expression has 2 + operators, we can look at the parenthesizations that group everything else first, giving us an expression of the form a + b + c. E.g., starting with 2 * 3 - 4 + 8 + 7 * 2, we can group ((2*3)-4) + 8 + (7*2), giving a = 2 * 3 - 4, b = 8, c = (7*2). Now, grouping this as either (a + b) + c or a + (b + c) will produce the same result. The same thing results when there are 2 * operators. If there are 3 - operators, we can group to get a - b - c - d, and now (a - (b - c)) - d = a - (b - (c - d)). This means that Catalan(N) is not obtainable for N > 4. But Catalan(4) is also not obtainable: the only possibility is to have one +, one *, and two - operators. But if the + precedes either -, we can group as a + b - c, and (a + b) - c = a + (b - c). So the + must follow both - operators - and now we can group as a - b - c + d, and (a - (b - c)) + d = a - (b - (c + d)). Catalan(3) is obtainable: 1 - 2 * 3 + 4 gives the values {1, -1, -7, -9, -13}. Also, 1 - 2 * 3 - 4 gives values {1, -1, 3, -7, -9} using just {- *}; however, {+ *} can produce Catalan(N) only for N <= 2. There are some sequences in the OEIS relating to the number of possible values you get when you just use exponentiation, with all numbers the same. See, e.g., A082499, which has links to some others. Franklin T. Adams-Watters -----Original Message----- From: mlb@well.com ... find the number of unique values of an infix expression (like say 1+2-3*4) parenthesized in all possible ways ... The operators were restricted to {+ - *}, the operands to positive integers. ... is there a method for constructing such expressions such that over parenthesization they give the maximum possible Catalan(N) unique values? What is the maximum achievable if the operators are restricted to {+ *} or {- *}? ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
(This doesn't reach math-fun@mailman.xmission.com because I'm not a member.) franktaw@netscape.net wrote:
In general, Catalan(N) unique values cannot be achieved.
Depends on the operator. It does not need to be commutative. Let's define (x @ y) = 1+ ( ( x + (x+y)^2 + 3y) / 2 ) Then (0 @ 0) = 1 (0 @ (0 @ 0)) = 3 ((0 @ 0) @ 0) = 2 (0 @ (0 @ (0 @ 0))) = 10 (0 @ ((0 @ 0) @ 0)) = 6 ((0 @ 0) @ (0 @ 0)) = 5 ((0 @ (0 @ 0)) @ 0) = 7 (((0 @ 0) @ 0) @ 0) = 4 etc. See http://www.research.att.com/~njas/sequences/A071653 (The graph looks nice, like fractal clouds of smoke from an old steam engine. I have to compute a b-file for this.) -- Antti
If the expression has 2 + operators, we can look at the parenthesizations that group everything else first, giving us an expression of the form a + b + c. E.g., starting with 2 * 3 - 4 + 8 + 7 * 2, we can group ((2*3)-4) + 8 + (7*2), giving a = 2 * 3 - 4, b = 8, c = (7*2). Now, grouping this as either (a + b) + c or a + (b + c) will produce the same result.
The same thing results when there are 2 * operators.
If there are 3 - operators, we can group to get a - b - c - d, and now (a - (b - c)) - d = a - (b - (c - d)).
This means that Catalan(N) is not obtainable for N > 4. But Catalan(4) is also not obtainable: the only possibility is to have one +, one *, and two - operators. But if the + precedes either -, we can group as a + b - c, and (a + b) - c = a + (b - c). So the + must follow both - operators - and now we can group as a - b - c + d, and (a - (b - c)) + d = a - (b - (c + d)).
Catalan(3) is obtainable: 1 - 2 * 3 + 4 gives the values {1, -1, -7, -9, -13}. Also, 1 - 2 * 3 - 4 gives values {1, -1, 3, -7, -9} using just {- *}; however, {+ *} can produce Catalan(N) only for N <= 2.
There are some sequences in the OEIS relating to the number of possible values you get when you just use exponentiation, with all numbers the same. See, e.g., A082499, which has links to some others.
Franklin T. Adams-Watters
-----Original Message----- From: mlb@well.com
... find the number of unique values of an infix expression (like say 1+2-3*4) parenthesized in all possible ways ... The operators were restricted to {+ - *}, the operands to positive integers.
... is there a method for constructing such expressions such that over parenthesization they give the maximum possible Catalan(N) unique values?
What is the maximum achievable if the operators are restricted to {+ *} or {- *}?
________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
-----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Antti Karttunen Sent: Wed 1/3/2007 5:42 PM To: seqfan@ext.jussieu.fr Cc: math-fun@mailman.xmission.com Subject: [math-fun] Re: puzzle family: values of parenthesized expressions (This doesn't reach math-fun@mailman.xmission.com because I'm not a member.) franktaw@netscape.net wrote:
In general, Catalan(N) unique values cannot be achieved.
Depends on the operator. It does not need to be commutative. Let's define (x @ y) = 1+ ( ( x + (x+y)^2 + 3y) / 2 ) Then (0 @ 0) = 1 (0 @ (0 @ 0)) = 3 ((0 @ 0) @ 0) = 2 (0 @ (0 @ (0 @ 0))) = 10 (0 @ ((0 @ 0) @ 0)) = 6 ((0 @ 0) @ (0 @ 0)) = 5 ((0 @ (0 @ 0)) @ 0) = 7 (((0 @ 0) @ 0) @ 0) = 4 etc. See http://www.research.att.com/~njas/sequences/A071653 (The graph looks nice, like fractal clouds of smoke from an old steam engine. I have to compute a b-file for this.) -- Antti
If the expression has 2 + operators, we can look at the parenthesizations that group everything else first, giving us an expression of the form a + b + c. E.g., starting with 2 * 3 - 4 + 8 + 7 * 2, we can group ((2*3)-4) + 8 + (7*2), giving a = 2 * 3 - 4, b = 8, c = (7*2). Now, grouping this as either (a + b) + c or a + (b + c) will produce the same result.
The same thing results when there are 2 * operators.
If there are 3 - operators, we can group to get a - b - c - d, and now (a - (b - c)) - d = a - (b - (c - d)).
This means that Catalan(N) is not obtainable for N > 4. But Catalan(4) is also not obtainable: the only possibility is to have one +, one *, and two - operators. But if the + precedes either -, we can group as a + b - c, and (a + b) - c = a + (b - c). So the + must follow both - operators - and now we can group as a - b - c + d, and (a - (b - c)) + d = a - (b - (c + d)).
Catalan(3) is obtainable: 1 - 2 * 3 + 4 gives the values {1, -1, -7, -9, -13}. Also, 1 - 2 * 3 - 4 gives values {1, -1, 3, -7, -9} using just {- *}; however, {+ *} can produce Catalan(N) only for N <= 2.
There are some sequences in the OEIS relating to the number of possible values you get when you just use exponentiation, with all numbers the same. See, e.g., A082499, which has links to some others.
Franklin T. Adams-Watters
-----Original Message----- From: mlb@well.com
... find the number of unique values of an infix expression (like say 1+2-3*4) parenthesized in all possible ways ... The operators were restricted to {+ - *}, the operands to positive integers.
... is there a method for constructing such expressions such that over parenthesization they give the maximum possible Catalan(N) unique values?
What is the maximum achievable if the operators are restricted to {+ *} or {- *}?
________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Antti Karttunen -
franktaw＠netscape.net -
Marc LeBrun -
Schroeppel, Richard