3

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$

Gaurang Tandon
  • 6,449
Jaska
  • 1,291
  • 5
    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 06 '10 at 21:15
  • True. I just heard a rumor that an elegant proof exists. – Jaska Nov 06 '10 at 21:28
  • 2
    If there's a non-brute force way of showing the desired result, I'd be very surprised. – J. M. ain't a mathematician Nov 07 '10 at 00:20
  • 3
    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, 10=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 07 '10 at 12:12

1 Answers1

2
from fractions import Fraction

def Jaska(L):
    if len(L) == 1:
        yield L[0], Fraction(L[0])
    else:
        for l in range(len(L) - 1):
            for e1, v1 in Jaska(L[:l+1]):
                for e2, v2 in Jaska(L[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

def JaskaAll(L):
    solutions = dict([])
    for e, v in Jaska(L):
        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.
Yuval Filmus
  • 57,157