Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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:















share|cite|improve this question
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
up vote 2 down vote accepted
from fractions import Fraction

def Jaska(L):
    if len(L) == 1:
        yield L[0], Fraction(L[0])
        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] = []
    return solutions

You can check

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

share|cite|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


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.