So here's the "general solution": A Python program that generates all expressions of the prescribed form (including parentheses) and evaluates them.
from __future__ import division
import itertools
def trees(n):
trs = [set('n')]
for i in range(1,n):
s = set()
for j in range(i):
for l in trs[j]:
for r in trs[i-j-1]:
s.add('(' + l + 'x' + r + ')')
trs.append(s)
return trs[-1]
def expressions(tree, n):
for i in range(n):
tree = tree.replace('n', str(i+1), 1)
for ops in itertools.product(['+', '-', '*', '/'], repeat=n-1):
t = tree
for o in ops:
t = t.replace('x', o, 1)
yield t
n = 9
num = 2015
for tree in trees(n):
for expr in expressions(tree, n):
try:
res = eval(expr)
if res == num:
print(str(num) + ' = ' + expr)
except ZeroDivisionError:
pass
Generating the parentheses is not a trivial task. This script generates "skeleton formulas" of the form ((nxn)xn)
, where n
is a placeholder for a number and x
is a placeholder for an operator, via dynamic programming (binary tree part taken from https://stackoverflow.com/a/12294488), then substitutes.
This is a very powerful approach. The program generates dozens of solutions in a matter of minutes (though not all of them are distinct after removing superfluous parentheses), e.g.
2015 = ((1-2)-((((3+((4-5)-6))*7)*8)*9))
2015 = ((1-2)-((((3*((4-5)-6))-7)*8)*9))
2015 = ((((1*2)+3)+((4*5)+6))*((7*8)+9))
2015 = ((1+((2*(3-4))-(5*6)))*(7-(8*9)))
2015 = ((1+((2/(3-4))-(5*6)))*(7-(8*9)))
2015 = ((1*(((2*(3+(4*(5*6))))+7)*8))-9)
2015 = (1*((2*(3-(4*(5*(6-(7*8))))))+9))
2015 = (((1*2)*(3+((4*5)*((6*7)+8))))+9)
2015 = ((1-2)-((3+((4-5)-6))*((7*8)*9)))
2015 = ((1*(((2*(3+((4*5)*6)))+7)*8))-9)
2015 = (((1*(((2+3)*4)+5))+6)*((7*8)+9))
2015 = (((1*(((2/3)/4)+5))*6)*((7*8)+9))
2015 = ((1*(2-3))-(4*(((5-6)*(7*8))*9)))
2015 = ((1*(2-3))-(4/(((5-6)/(7*8))/9)))
2015 = ((1/(2-3))-(4*(((5-6)*(7*8))*9)))
2015 = ((1/(2-3))-(4/(((5-6)/(7*8))/9)))
2015 = (((1*2)-3)-(((4*(5-6))*(7*8))*9))
2015 = (((1*2)-3)-(((4/(5-6))*(7*8))*9))
2015 = (((((1-2)-3)/4)-(5*6))*(7-(8*9)))
and can indeed be used to exhaust the entire search space and also solve a number of generalizations of the original problem.
As an example of the latter, the program reveals the existence of solutions with only the first eight digits:
$$2015 = 1-2-(3-4-5)\times6\times7\times8$$
and can also prove in just a few seconds that with only the first seven digits, no solution exists.