[voider]

If you have 7 integer variables, e.g. a, b, c, d, e, f, g, and you can use each at most once in an expression with the operators +, -, *, / (integer division), how many unique expressions can be formed?

E.g. (a - b) * c + f is mathematically the same as:

c * (a - b) + f

f + (a - b) * c

f + c * (a - b)

so they all correspond to a single unique expression.

If there was one variable, there are 7 unique expressions.

With two variables, I think there are 133 unique expressions.

I don't know the answer (yet), and I very much doubt anyone can find a closed form formula for the general problem. About the context where this problem originated, I suspect it was intended to be virtually unsolvable... (and deceptively mediocre-looking)

[Guest]

with one variable, i only get 2 unique expressions with those operators. a and -a.

i would be interested to see how you get 133, with 2.

the only ones i see are...

a +b

a -b

a *b

a /b

-a +b

-(a +b)

-a*b

-a/b

anything else is essentially the same operation.

[BobbyGo]

When voider said one variable, I think he meant ANY one variable (a or b or c ... or g) to make 7 unique expressions. Counting the negatives would turn that into 14.

[Guest]

with one variable, i only get 2 unique expressions with those operators. a and -a.

i would be interested to see how you get 133, with 2.

the only ones i see are...

a +b

a -b

a *b

a /b

-a +b

-(a +b)

-a*b

-a/b

anything else is essentially the same operation.

If I understand the problem, then you need to add four more to your list for 2 variables:

a

b

-a

-b

voider said "....you can use each at most once..."

Edited November 9, 2011 by thoughtfulfellow

[Guest]

I don't think you can count a AND -a as two expressions. If it is a unique integer variable, then using it's negative creates a new value all together. ie, you can't say that 7 and -7 are the same integer. And I don't think using "-" as an argument of an operator is valid either?

[voider]

Clarification:

The operators are binary.

If there was one variable...

With two variables...

I was not clear on this.

What I meant was, still assuming there are 7 variables:

The number of expressions with exactly one variable is 7: a, b, c, d, e, f, g

The number of expressions with two or less variables (i.e. including the 7) is 133: a, b, c, d, e, f, g, a + b, a - b, a * b, a / b, ..., f / g, ... g / a.

I have an answer now.

[Guest]

Assuming that all variables are nonzero,there should be 84 not 133 possible operations with 2 variables

7C2*4=84

[voider]

133 is correct, = 7C2 * 6 + 7

37766040

There are several subproblems that have to be combined optimally:

1. Iterating through order 4^6 operator combinations

2. Iterating through order 2^10 postfix expressions

3. Iterating through order 7! variable combinations

While this method is faster than brute force it is still very slow. If anyone finds an optimization based on a revelational observation that changes the need to "try almost everything" please let me know.