How can one get $2015$ using $1,2,\dots,9$ in this order and only once, with the operations $+,-,\times,/$ ?
Solving this riddle with a computer (using python) turned out to be impossible for me due to the amount of memory needed.
Hence, I am looking for a mathematical way to find the/a solution (I am not just looking for the solution, but also for a technique to solve that kind of problems).
On
One technique is to use a product of numbers to get close to the solution and then use the remaining numbers to correct: For example $7\times8\times9=504=\frac{1}{4}\times2016$. Hence we need to generate a factor of $-1$ to add, and a factor of $4$ to multiply. One solution using this idea is
$$-1+(2-3+4-5+6)\times7\times8\times9$$
Another technique is to attempt to use a factorization: $2015=31\times65$ for example. Noting that $-7+8\times9=65$, all we have left to do is generate a factor of $31$. A solution using this idea is $$((1-2)\times(3-4)+5\times6)\times(-7+8\times9)$$
On
I did this: $2015+9=2024$
$2024\div 8=253$
$253-7=246$
$246\div 6=41$
$41-5=36$
$36\div 4=9$
$9\div 3=3$
$3-2=1$
$1-1=0$.
Then $2015=(((1+2)\cdot 3\cdot 4+5)\cdot 6+7)\cdot 8-9$
On
$$ \begin{align} 2015 &=-1+2016\\ &=-1+224\times9\\ &=-1+28\times8\times9\\ &=-1+4\times7\times8\times9\\ &=-1+2\times2\times7\times8\times9\\ &=-1+2\times(-3+4-5+6)\times7\times8\times9\\ \end{align} $$ The "method" used above was to look for a number close to 2015 that has a number of factors. Use a combination of early integers to make up the difference and the rest to make up the factors. Here, $2015+1=2016=4\times7\times8\times9$. This reduces the problem to writing $4$ using $2,3,4,5,6$. A similar approach was used to break $4=2\times2$ where now the problem is reduced to writing $2$ using $3,4,5,6$.
On
A simple brute force Python program could be used to find one possible solution, although finding all possible solutions would require permuting parentheses as well.
target = 2015
def rec(seq, total, ops):
if (seq == 10):
if total == target:
print ops
return
rec(seq+1, total*seq, ops + ['*'])
rec(seq+1, total-seq, ops + ['-'])
rec(seq+1, total+seq, ops + ['+'])
rec(seq+1, float(total)/seq, ops + ['/'])
rec(1, 0, [])
This program returns:
['+', '+', '*', '*', '+', '*', '+', '*', '-']
which is a possible solution to the problem
$(((1+2)*3*4+5)*6+7)*8-9 = 2015$
On
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.
On
A very easy approach can be
A) Find the prime factors of the number. That is,
$$5\times13\times31=2015$$
B) Express those prime factors as sum,difference,product and divison of numbers $1-9$, starting from the biggest prime factor to be easy. That is,
$$ (8-3)\times(7\cdot2-1)\times(9\cdot4-5)$$
Just one example. :)
Peter Woolfitt's answer gives two good approaches to solving this type of problem, but his methods are far from the full story. Using Mathematica, I ran an exhaustive search over all possible parenthesizations of all possible arrangements of $+, -, \times, \div$ among the digits 1 through 9, and came up with 536 distinct* solutions, listed below. There are simply so many ways to combine 9 numbers with 4 operations that no single high-level method can discover them all.
Note that my program distinguishes between different parenthesizations of commutative operations, e.g.
((1 + 2) + 3)and(1 + (2 + 3))would be considered two distinct solutions. Also, I have only searched for solutions using $-$ as an infix (subtraction) operator, not a unary (negation) operator.