Generate all numbers from 1- 20 using 5,10,15,20 using operators *,/,+,-,^

Question

I have to make all the numbers from 1-20 using the operators *,/,+,-,^ and the numbers 5,10,15,20.

Specifically, how I make 14 and 16?

Edit: Every number has to be used and only once. Parentheses are allowed. Operators can be used to any amount as required.

Answer 1

It's simply impossible. Proof: brute force

c++ code (Edit: sorry for the bump, but I've improved greatly the code I included to generalize operations [now accounts for exponents], so I can definitively say there is no way to make 14 and 16 based on a brute force search):

typedef int Digit;

constexpr Digit numDigits{4};
constexpr Digit target{24};

typedef float (*Operator)(float, float);
typedef std::map<char, Operator> Operators;

// operators
float add(float a, float b) {return a+b;}
float subtract(float a, float b) {return a-b;}
float multiply(float a, float b) {return a*b;}
float divide(float a, float b) {return a/b;}
float power(float a, float b) {return powf(a,b);}

const Operators operators = {{'+', add}, {'-', subtract}, {'*', multiply}, {'/', divide}, {'^', power}};
const std::map<Operator, char> operators_inverse = flip_map(operators);  // new map with keys and values swapped

typedef std::array<Digit, numDigits> digits;
digits d;

void print_solution(const std::array<Digit, numDigits>& nums, std::vector<char> &ops) {
    std::string accum (numDigits-2, '(');
    for(unsigned i=0; i<numDigits-1; ++i) {
        accum += std::to_string(nums[i]);
        if (i!=0) accum += ')';
        accum += std::string(&ops[i], 1);
    }
    accum += std::to_string(nums[numDigits-1]);
    printf("%s\n",accum.c_str());
}

int main() {

    d = {3,6,10, 4};

    if(std::accumulate(d.begin(), d.end(), 0) == target) {
        std::vector<char> v(numDigits-1,'+');
        print_solution(d, v);
    }
    if(std::accumulate(d.begin(), d.end(), 1, multiply) == target) {
        std::vector<char> v(numDigits-1,'*');
        print_solution(d, v);
    }

    auto keys = map_keys(operators);   // vector of map keys
    auto ops = map_values(operators);  // vector of map values
    std::sort(d.begin(), d.end());
    std::sort(ops.begin(), ops.end());
    do {
        do{
            float last = ops[0](d[0], d[1]);   // init with inner-most value

            for(unsigned i=1; i<numDigits-1; ++i) {  // - 2 cause there are |d|-1 operators
                last = ops[i](d[i+1], last);
            }

            if(last == target) {
                std::vector<char> v;
                for(Operator o : ops) {
                    v.push_back(operators_inverse.at(o));
                }
                print_solution(d, v);
            }
        } while (std::next_permutation(d.begin(), d.end()));
    } while (std::next_permutation(ops.begin(), ops.end()));

    return 0;
}

Answer 2

Here's another program that evaluates all the well-formed RPN (Reverse Polish Notation) strings made up with numbers $\{5,10,15,20\}$ and operators $\{+,*,-,/,\hat{}\}$.

""" Make numbers in range(1,21) out of {5, 10, 15, 20} with {+ - * / ^}.
    Each number must be used exactly once.
    The program forms RPN strings and evaluates them, reporting those that
    produce integers in the range from 1 to 20 (included).
"""

from __future__ import print_function

def eval_rpn(s):
    """ Evaluates RPN string. """
    global rcnt, ucnt
    es = []
    for x in s:
        if x in numbers:
            es.append(float(x))
        else:
            v2 = es.pop()
            v1 = es.pop()
            if x == '+':
                es.append(v1+v2)
            elif x == '*':
                es.append(v1*v2)
            elif x == '-':
                es.append(v1-v2)
            elif x == '/':
                if v1 % v2 != 0:
                    raise ValueError
                es.append(v1/v2)
            elif x == '^':
                es.append(v1**v2)
            else:
                raise RuntimeError()
    if len(es) != 1:
        raise RuntimeError()
    value = es[0]
    if value in range(1,21):
        rcnt += 1
        print(', '.join(s), '=', value)
        if not value in sample:
            sample[value] = s
    if value in [14, 16]:
        ucnt += 1
        print('******** whoa! ********')

def pick_cand_tk(s, nums):
    """ Picks all tokens that may be used to extend RPN string. """
    cand = []
    for n in numbers:
        if not n in s:
            cand.append(n)
    if 2*nums - len(s) > 1:
        cand.extend(['+', '*', '-', '/', '^'])
    return cand

def rpn_recur(s,nums):
    """ Recursively construct well-formed RPN strings. """
    global tcnt
    if len(s) == 7:
        try:
            eval_rpn(s)
        except (OverflowError, ZeroDivisionError, ValueError):
            pass
        tcnt += 1
    else:
        for c in pick_cand_tk(s, nums):
            rpn_recur(s + [c], nums + (c in numbers))


numbers = ['5', '10', '15', '20']
tcnt = 0 # total number of leaves
rcnt = 0 # number of leaves whose evaluation is in range(1,21)
ucnt = 0 # number of unexpected values
sample = {}
rpn_recur([], 0)

print('leaves: total =', tcnt, ' in-range =', rcnt, ' unxepected =', ucnt)
for k in sample:
    print(int(k), '->', ', '.join(sample[k]))

The program examines 15000 RPN strings, finds that than 852 evaluate to an integer between 1 and 20, also finds that no string evaluates to either 14 or 16, and finally prints examples of how to obtain the other numbers in the range.

Computations are carried out with integer values throughout. This excludes results like $(20/5)^{15/10} = 8$. To include them, one comments out the check on the $0$ remainder in eval_rpn. In any case, $14$ and $16$ remain off limits.