How to make from 123456789 the number 100 or 0

    In the “Entertaining Arithmetic” of the famous popularizer of sciences Yakov Isidorovich Perelman at the end of the first chapter I found an example of the following “Arithmetic Curiosities”:

    100 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9
    100 = 12 + 3-4 + 5 + 67 + 8 + 9
    100 = 12-3-4 + 5-6 + 7 + 89
    100 = 123 + 4-5 + 67-89
    100 = 123-45-67 + 89

    The first of these solutions I found more in elementary school at the Mathematics Olympiad, and now thinking that maybe that victory influenced my future formation, I decided to pay tribute to this task and find all possible solutions by writing the appropriate Python script.

    Let the task be stated as follows: there is a line of digits 123456789 (even though I really am not very interested in zero), between which you can put 4 arithmetic operations (+, -, *, /) in any place or not put anything (that is, put an empty line, then two- or more-digit numbers are formed) so that the general expression yields 100 as a result, as in the examples from the book above. Nothing else is allowed, no brackets, no permutations, no takes, no kicks.

    I did not study programming, and I realized the task as I came up with. So I have a question: "How it could have been done better?" .

    And I came up with this: in order to sort through all the possible options for inserting the characters of the spaces (and there are five of them: either an empty string, or +, -, *, /), I presented them as variants of the number on the base 5, supplemented with zeros on the left. The length of this number is eight characters, because the numbers are nine, and then there are eight spaces between them. Zeros correspond to empty lines, all the rest to arithmetic operations. Here's what happened:

    Copy Source | Copy HTML
    from __future__ import division # for 2.x version
     
    s = '123456789'
    d = {'0':'', '1':'+', '2':'-', '3':'*', '4':'/'}
    sum_num = 100
    count =  0
     
    def to_new_base(n, new_base):
        s = []
        if n ==  0:
            s.append('0')
        while n:
            s.append(str(n % new_base))
            n = n // new_base
        num = '{0:0>8}'.format(''.join(s[::-1]))
        return num
     
     
    for n in xrange(int('44444444', 5)):
        num = to_new_base(n, 5)
        expr = ''
        for i, j in zip(s, num):
            expr += i + d[j]
        expr += '9'
        if eval(expr) == sum_num:
            print('{0} = {1}'.format(expr, sum_num))
            count += 1
     
     
    print 'So, {0} expressions for {1}'.format(count, sum_num)


    For 100 there were 101 such solutions, and some of them are quite funny, especially with fractions:

    123 + 45-67 + 8-9 = 100
    123 + 4-5 + 67-89 = 100
    123 + 4 * 5-6 * 7 + 8-9 = 100
    123-45-67 + 89 = 100
    123-4-5-6-7 + 8-9 = 100
    12 + 34 + 5 * 6 + 7 + 8 + 9 = 100
    12 + 34-5 + 6 * 7 + 8 + 9 = 100
    12 + 34-5-6 + 7 * 8 + 9 = 100
    12 + 34-5-6-7 + 8 * 9 = 100
    12 + 3 + 4 + 5-6-7 +89 = 100
    12 + 3 + 4-56 / 7 + 89 = 100
    12 + 3-4 + 5 + 67 + 8 + 9 = 100
    12 + 3 * 45 + 6 * 7-89 = 100
    12 + 3 * 4 + 5 + 6 + 7 * 8 + 9 = 100
    12 + 3 * 4 + 5 + 6-7 + 8 * 9 = 100
    12 + 3 * 4-5-6 + 78 + 9 = 100
    12-3 + 4 * 5 + 6 + 7 * 8 + 9 = 100
    12-3 + 4 * 5 + 6-7 + 8 * 9 = 100
    12-3-4 + 5-6 + 7 + 89 = 100
    12-3-4 + 5 * 6 + 7 * 8 + 9 = 100
    12-3-4 + 5 * 6-7 + 8 * 9 = 100
    12 * 3-4 + 5-6 + 78-9 = 100
    12 * 3-4-5-6 + 7 + 8 * 9 = 100
    12 * 3-4 * 5 + 67 + 8 + 9 = 100
    12/3 + 4 * 5-6-7 + 89 = 100 12/3 +
    4 * 5 * 6-7-8-9 = 100 12/3
    + 4 * 5 * 6 * 7 / 8-9 = 100 12/3
    / 4 + 5 * 6 + 78-9 = 100
    1 + 234-56-7-8 * 9 = 100
    1 + 234 * 5 *
    6/78 + 9 = 100 1 + 234 * 5 / 6-7-89 = 100
    1 + 23-4 + 56 + 7 + 8 + 9 = 100
    1 + 23-4
    + 56/7 + 8 * 9 = 100 1 + 23-4 + 5 + 6 + 78-9 = 100
    1 + 23-4 -5 + 6 + 7 + 8 * 9 = 100
    1 + 23 * 4 + 56/7 + 8-9 = 100
    1 + 23 * 4 + 5-6 + 7-8 + 9 = 100
    1 + 23 * 4- 5 + 6 + 7 + 8-9 = 100
    1 + 2 + 34-5 + 67-8 + 9 = 100
    1 + 2 + 34 * 5 + 6-7-8 * 9 = 100
    1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9 = 100
    1 + 2 + 3-45 + 67 + 8 * 9 = 100
    1 + 2 + 3-4 + 5 + 6 + 78 + 9 = 100
    1 + 2 + 3- 4 * 5 + 6 * 7 + 8 * 9 = 100
    1 + 2 + 3 * 4-5-6 + 7 + 89 = 100
    1 + 2 + 3 * 4 * 56 / 7-8 + 9 = 100
    1 + 2 + 3 * 4 * 5/6 + 78 + 9 = 100
    1 + 2-3 * 4 + 5 * 6 + 7 + 8 * 9 = 100
    1 + 2-3 * 4-5 + 6 * 7 + 8 * 9 = 100
    1 + 2 * 34-56 + 78 + 9 = 100
    1 + 2 * 3 + 4 + 5 + 67 + 8 + 9 = 100
    1 + 2 * 3 + 4 * 5-6 + 7 + 8 * 9 = 100
    1 + 2 * 3-4 + 56/7 + 89 = 100
    1 + 2 * 3-4-5 + 6 + 7 + 89 = 100
    1 + 2 * 3 * 4 * 5/6 + 7 + 8 * 9 = 100
    1-23 + 4 * 5 + 6 + 7 + 89 = 100
    1-23-4 + 5 * 6 + 7 + 89 = 100
    1-23-4-5 + 6 * 7 + 89 = 100
    1-2 + 3 + 45 + 6 + 7 * 8-9 = 100
    1-2 + 3 * 4 + 5 + 67 + 8 + 9 = 100
    1-2 + 3 * 4 * 5 + 6 * 7 + 8-9 = 100
    1-2 + 3 * 4 * 5-6 + 7 * 8-9 = 100
    1-2-34 + 56 + 7 + 8 * 9 = 100
    1-2-3 + 45 + 6 * 7 + 8 + 9 = 100
    1-2-3 + 45-6 + 7 * 8 + 9 = 100
    1-2-3 + 45-6-7 + 8 * 9 = 100
    1-2-3 + 4 * 56/7 + 8 * 9 = 100
    1-2-3 + 4 * 5 + 67 + 8 + 9 = 100
    1-2 * 3 + 4 * 5 + 6 + 7 + 8 * 9 = 100
    1-2 * 3-4 + 5 * 6 + 7 + 8 * 9 = 100
    1-2 * 3-4-5 + 6 * 7 + 8 * 9 = 100
    1 * 234 + 5-67-8 * 9 = 100
    1 * 23 + 4 + 56/7 * 8 + 9 = 100
    1 * 23 + 4 + 5 + 67-8 + 9 = 100
    1 * 23-4 + 5-6-7 + 89 = 100
    1 * 23-4-56 / 7 + 89 = 100
    1 * 23 * 4-56 / 7/8 + 9 = 100
    1 * 2 + 34 + 56 + 7-8 + 9 = 100
    1 * 2 + 34 + 5 + 6 * 7 + 8 + 9 = 100
    1 * 2 + 34 + 5-6 + 7 * 8 + 9 = 100
    1 * 2 + 34 + 5- 6-7 + 8 * 9 = 100
    1 * 2 + 34-56 / 7 + 8 * 9 = 100
    1 * 2 + 3 + 45 + 67-8-9 = 100
    1 * 2 + 3 + 4 * 5 + 6 + 78-9 = 100
    1 * 2 + 3-4 + 5 * 6 + 78-9 = 100
    1 * 2 + 3 * 4 + 5-6 + 78 + 9 = 100
    1 * 2-3 + 4 + 56 / 7 + 89 = 100
    1 * 2-3 + 4-5 + 6 + 7 + 89 = 100
    1 * 2-3 + 4 * 5-6 + 78 + 9 = 100
    1 * 2 * 34 + 56-7-8 -9 = 100
    1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9 = 100
    1 * 2 * 3-45 + 67 + 8 * 9 = 100
    1 * 2 * 3-4 + 5 + 6 + 78 + 9 = 100
    1 * 2 * 3-4 * 5 + 6 * 7 + 8 * 9 = 100
    1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9 = 100
    1 * 2 * 3 * 4 + 5 + 6-7 + 8 * 9 = 100
    1 * 2 * 3 * 4-5-6 + 78 + 9 = 100
    1 * 2/3 + 4 * 5 / 6 + 7 + 89 = 100
    1/2 * 34-5 + 6-7 + 89 = 100
    1/2 * 3/4 * 56 + 7 + 8 * 9 = 100
    1/2/3 * 456 + 7 + 8 + 9 = 100

    Then I decided to look at the complete dependence of the number of possible solutions to such decompositions on all possible sums, including non-integer ones. For this, the cycle has become a function that works on filling out the dictionary:

    Copy Source | Copy HTML
    figure = {}
    xlist = []
    ylist = []
     
    def func():
        for n in range(int('44444444', 5)):
            num = to_new_base(n, 5)
            expr = ''
            for i, j in zip(line, num):
                expr += i + d[j]
            expr += '9'
            num_sum = eval(expr)
            if num_sum in figure:
                figure[num_sum] += 1
            else:
                figure[num_sum] = 1
     
        for key in sorted(figure):
            xlist.append(key)
            ylist.append(figure[key])


    The dependency lists ylist = f (xlist) are drawn using matplotlib. The dependency has a peak at zero with 167 solutions: The



    left branch is not symmetrical to the right, because before the option 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, by the condition of the problem, we can’t put minus. The closer to zero, the more often there are real numbers that can be represented in several possible ways.









    A separate consideration for solutions in the field [-1.1, 1.1]: the largest number of solutions falls, in fact, to zero, then to integers -1, 1, then half-integers -0.5, 0.5.



    It is verified that any of the integers from 0 to 100 can be expressed in this way:



    Maybe this task will be liked just to ask someone, for example, their own child or friend, on the speed of counting and the ability to handle numbers, as it was once given to me in elementary school and it was necessary to find one solution, although, as I see now, there were many more. And you can try it yourself in your mind or on paper to find at least one of the 167 solutions for scratch.

    UPD: Do not think that all these graphs are something serious. There is nothing serious here, apart from setting the task, code, and suggesting to pythonists to try to write something faster.

    UPD2: A great option for improving the code was written in hellman's comment

    Also popular now: