Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
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 6 '10 at 21:15
    
True. I just heard a rumor that an elegant proof exists. –  Jaska Nov 6 '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. Nov 7 '10 at 0:20
2  
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

1 Answer 1

up vote 2 down vote accepted
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.