# A problem related to the number 1963

You are allowed to use +, -, / and * (plus, minus, division and multiplication) signs and bracketing. These signs you can put between the numbers

1963

to form mathematical expressions. You must put at least one sign between two numbers and – cannot be used as “negative”, thus -1+9+6+3 is not allowed, but 1-9+6+3 is allowed.

The question is: what is the smallest natural number that cannot be expressed in this way? How to show (elegantly, without computer) that it is impossible to get 14?

I found myself the following representations:

$0=1*9-6-3$

$1=(1/9)*(6+3)$

$2=1+9/(6+3)$

$3=1*9/(6-3)$

$4=1+9/(6-3)$

$5=(1+9)/(6/3)$

$6=1*9-6+3$

$7=1+9-6+3$

$8=1+9-6/3$

$9=1*(9-6)*3$

$10=1+(9-6)*3$

$11=1*9+6/3$

$12=1+9+6/3$

$13=1+9+6-3$

-
There is rarely an elegant proof that some number is impossible. With the restricted class of operators, a computer search is pretty easy. I can't find 14, either. – Ross Millikan Nov 6 '10 at 21:15
True. I just heard a rumor that an elegant proof exists. – Jaska Nov 6 '10 at 21:28
If there's a non-brute force way of showing the desired result, I'd be very surprised. – J. M. Nov 7 '10 at 0:20
Could someone say if the following is true? If we work in Z/3Z then we have integers 1, 0, 0, 0 and 2. But 1+0=1, 1*0=0, 1-0=0 so we have to use division at least once. If we form a fraction then we see that denominator is divisible by 3, so numerator should also be divisible by three. Therefore the expression is of the form 1*(something)=14, where something contains numbers {x/3,y,z} for some {x,y,z}={3,6,9}. Now to get 2 mod 3, we see that x must be 6 so the original expression is 1*(9A6/3) where A is one of +, -, *, /. I checked every case and found no solution. – Jaska Nov 7 '10 at 12:12

from fractions import Fraction

if len(L) == 1:
yield L[0], Fraction(L[0])
else:
for l in range(len(L) - 1):
yield '(%s + %s)' % (e1, e2), v1 + v2
yield '(%s - %s)' % (e1, e2), v1 - v2
yield '(%s * %s)' % (e1, e2), v1 * v2
if v2 != 0:
yield '(%s / %s)' % (e1, e2), v1 / v2

solutions = dict([])
if v.denominator == 1:
v = v.numerator
if v not in solutions:
solutions[v] = []
solutions[v].append(e[1:-1])
return solutions


You can check

14 in JaskaAll([1,9,6,3])
to make sure.

-
Outputs nothing. – Jaska Nov 7 '10 at 12:27
With Yuvel Filmus's answer: print JaskaAll(14) To see the result, they are just function definitions. – Alec Teal May 3 '13 at 9:13
Have you tried this? I believe that the correct input is the list [1,9,6,3] rather than 14. – Yuval Filmus May 3 '13 at 13:36