3
$\begingroup$

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$

  • 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.2010-11-06
  • 0
    True. I just heard a rumor that an elegant proof exists.2010-11-06
  • 2
    If there's a non-brute force way of showing the desired result, I'd be **very** surprised.2010-11-07
  • 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, 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.2010-11-07

1 Answers 1

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.

  • 0
    Outputs nothing.2010-11-07
  • 0
    With Yuvel Filmus's answer: `print JaskaAll(14)` To see the result, they are just function definitions.2013-05-03
  • 0
    Have you tried this? I believe that the correct input is the list [1,9,6,3] rather than 14.2013-05-03