2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ do you have to use all the numbers and operators? $\endgroup$ – Dando18 Jul 17 '17 at 15:45
  • 1
    $\begingroup$ Perhaps it'd be helpful if we could see a few examples - say 1-10. In addition, I presume we can't use numbers/operators more than once? Are parentheses allowed? $\endgroup$ – Shuri2060 Jul 17 '17 at 15:49
  • $\begingroup$ Every number has to be used and only once. Parentheses are allowed. Operators can be used to any amount as required $\endgroup$ – Neo TheOne Jul 17 '17 at 15:51
  • 1
    $\begingroup$ must also make use of $15$ $\endgroup$ – Alvin Lepik Jul 17 '17 at 16:03
  • 1
    $\begingroup$ @fonfonx You'd be able to make any number with the ++ and -- operators trivially. They are different from + and -, and are used in programming. $\endgroup$ – Shuri2060 Jul 17 '17 at 16:15
4
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ The code is nice. Do you have some output as far as the unique values returned by this code between say 1 and 100? $\endgroup$ – abiessu Jul 17 '17 at 16:29
  • $\begingroup$ I think it's best to include powers - you could still have (.^.)+(.^.), for example (although I agree that it's probably still impossible). $\endgroup$ – Shuri2060 Jul 17 '17 at 16:45
  • $\begingroup$ @Shuri2060 actually I decided not to include them based off of the comment and the fact that I lazily hardcoded in operator combinations so incorporating powers would greatly increase the size of the code. I'm working on a more general solution rn in mathematica and I'll make sure to account for powers. $\endgroup$ – Dando18 Jul 17 '17 at 16:52
  • 1
    $\begingroup$ Nice use of std::next_permutation. $\endgroup$ – Fabio Somenzi Jul 17 '17 at 18:50
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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