Using + - * / operators and 4 4 4 4 digits find all formulas that would resolve to 1 2 3 4 5 6 7 8 9 10

Question

I had a conversation with a colleague of mine and he brought up an interesting problem. Using the + - * / operators and four 4 4 4 4 digits, create an algorithm that will output all the formulas that would equate to 1 or 2 or 3 or 4 or 5 or 6 or 7 or 9 or 10

Example of results

1 = (4/4/4)*4  
2 = (4*4)/(4+4)  
3 = (4+4+4)/4  
4 = 4+(4*(4-4))  
5 = ((4*4)+4)/4  
6 = 4+((4+4)/4)  
7 = (4+4)-(4/4)  
8 = (4/4)*(4+4)  
9 = (4+4)+(4/4)  
10 = (44-4)/4  

But is should output all possible combinations of the above example.

The question is not what the resulting formulas are but how should I approach creating the algorithm that produces the desired result under specific conditions like the ones above.

Answer 1

Create a recursion that uses the reverse Polish notation. Here is a pseudo-code:

function rec(digitsLeft, numbers, operators, expression):
    if digitsLeft == 0 and numbers - operators == 1:
        value = evaluate(expression)
        if value in {1..10}: output expression
        return
    if digitsLeft > 0:
        rec(digitsLeft - 1, numbers + 1, operators, [expression, 4])
    if digitsLeft > 1:
        rec(digitsLeft - 2, numbers + 1, operators, [expression, 44])
    if numbers - operators > 1:
        for op in ['+', '-', '*', '/']:
            rec(digitsLeft, numbers, operators + 1, [expression, op])

The reverse Polish notation will take care of operators' precedence, so you don't have to handle brackets.

The initial call is:

rec(4, 0, 0, [])

and the parameters are:

• digitsLeft -- how many digits do we still need to use,
• numbers -- how many numbers our expression already has,
• operators -- how many operators our expression already has,
• expression -- the array holding the elements of the expression.

Of course, you need to write evaluate (the function that evaluates expression) and output (the function that will most likely convert the reverse Polish notation expression to the standard infix notation (using some of the known algorithms, for example this one) and print it to the screen or a file).

A more general version would replace this:

    if digitsLeft > 0:
        rec(digitsLeft - 1, numbers + 1, operators, [expression, 4])
    if digitsLeft > 1:
        rec(digitsLeft - 2, numbers + 1, operators, [expression, 44])

with a loop that would go through $4$, $44$, etc., but for this example, it was easier to do just a copy/paste of two if-s.

If you need any further clarification, please ask.

Answer 2

I suggest you use recursion. If $S(k)$ are all the formulas using $k$ 4's, a formula using $k+1$ 4's is either

$A + B$, $A * B$, $A - B$, $A / B$ where $A$ and $B$ use $j$ and $k+1-j$ 4's respectively, $j = 1 \ldots k$, or it is the concatenation of $k+1$ 4's.

Construct each formula, evaluate carefully (watch out for division by $0$), and select those where the result is one of the desired ones.

Answer 3

I am presenting a self-contained GUILE Scheme program that accomplishes what you want. To see individual solutions, for example the representations of the range $26$ to $32$ by four fours, type the following command:

guile> (load "ff.scm")
guile> (table-display 4 26 27 28 29 30 31 32)
28 (44) - ((4) * (4)); (((4) + (4)) * (4)) - (4);
32 ((4) * (4)) + ((4) * (4));

Another example is

guile> (table-display 4 11 12 13 14)
12 ((44) + (4)) / (4); ((4) - ((4) / (4))) * (4);

As there can be quite a few solutions for some target values there is another command to display just the counts for the solutions from a certain range plus one representative formula. Responding to the poster's question we can display the counts for the range from one to ten/twenty:

guile> (table-query-ints 4 1 20)
1 25: (4) / (((4) - (4)) + (4))
2 5: (4) / (((4) + (4)) / (4))
3 2: (((4) + (4)) + (4)) / (4)
4 4: (4) - (((4) - (4)) * (4))
5 1: (((4) * (4)) + (4)) / (4)
6 1: (((4) + (4)) / (4)) + (4)
7 4: (4) - (((4) / (4)) - (4))
8 20: (4) / ((4) / ((4) + (4)))
9 3: ((4) + (4)) + ((4) / (4))
10 1: ((44) - (4)) / (4)
12 2: ((44) + (4)) / (4)
15 2: ((4) * (4)) - ((4) / (4))
16 20: (4) - ((4) - ((4) * (4)))
17 2: ((4) * (4)) + ((4) / (4))
20 1: (((4) / (4)) + (4)) * (4)

It would be interesting to see these counts being confirmed with a different programming language. This is the source of the program:

(define table-memo
  (let ((vals (make-hash-table)))
    (lambda (count)
      (let ((val (hash-ref vals count)))
       (if (not (hash-table? val))
           (begin
             (set! val (table-compute count))
             (hash-set! vals count val))) val))))

(define table-display
  (lambda (count . what)
    (hash-for-each
     (lambda (v l)
       (if (or (null? what) (member v what))
          (begin
            (format #t "~a" v)
            (for-each
             (lambda (ent)
              (format #t " ~a;" ent)) l)
            (newline)))) (table-memo count))))

(define table-query-ints
  (lambda (count minval maxval)
    (let ((t (table-memo count)))
      (letrec
         ((iter 
           (lambda (val)
             (if (<= val maxval)
                (let ((lookup (hash-ref t val)))
                  (if (list? lookup)
                     (format #t "~a ~a: ~a~%"
                            val (length lookup) (car lookup)))
                  (iter (1+ val)))))))
       (iter minval)))))



(define table-compute
  (lambda (count)
    (let ((res (make-hash-table)))
      (letrec
         ((concat4
           (lambda (k)
             (if (= k 1) 4 
                (+ (* 10 (concat4 (- k 1))) 4))))
          (record
           (lambda (val str)
             (let ((lookup (hash-ref res val)))
              (if (list? lookup)
                  (hash-set! res val (cons str lookup))
                  (hash-set! res val (list str))))))
          (combine-ents
           (lambda (val1 list1 c1 val2 list2 c2)
             (for-each
              (lambda (ent1)
               (for-each
                (lambda (ent2)
                  (if (<= c1 c2)
                     (record
                      (+ val1 val2) 
                      (format #f "(~a) + (~a)" ent1 ent2)))
                  (if (<= c1 c2)
                     (record
                      (* val1 val2) 
                      (format #f "(~a) * (~a)" ent1 ent2)))
                  (record
                   (- val1 val2) 
                   (format #f "(~a) - (~a)" ent1 ent2))
                  (if (not (zero? val2))
                     (record
                      (/ val1 val2) 
                      (format #f "(~a) / (~a)" ent1 ent2))))
                  list2)) list1)))
          (iter
           (lambda (q)
             (if (< q count)
                (begin
                  (let ((left (table-memo q)) 
                       (right (table-memo (- count q))))
                    (hash-for-each
                     (lambda (v1 l1)
                      (hash-for-each
                       (lambda (v2 l2)
                         (combine-ents v1 l1 q v2 l2 (- count q)))
                       left)) right))
                  (iter (1+ q)))))))
        (let* ((c4 (concat4 count)))
          (hash-set! 
           res c4 (list (number->string c4)))
          (iter 1))) res)))     

I posted a similar program some time ago and I will send the link if I can find it.

EDIT
The previous post that I alluded to can be found here at MSE. With the above I made an extra effort to keep it as compact and simple as possible.

Reading the code carefully you will see that it generates products and sums only once, even though they can be represented by two expression trees.

The code includes expressions where zero appears as an intermediate value. It is not difficult to check for this and prevent it from ocurring if desired.

Answer 4

As an extension, rather than an answer ... If radicals and/or factorials are added to the set of operators, then the number of ways one can combine the digits of an integer changes from being a finite combinatorical problem to an infinite one. This is because one can repeatedly nest the √ and ! operators to any arbitrary depth (for example, 4!!!!!!!).

A few years ago, I wrote some code in Mathematica to do this, to arbitrary level of nesting. For the problem at hand (4444), and allowing radicals, here is some sample output (only the first 9 variations for each number are shown here):

To view a magnified version: http://www.tri.org.au/se/4444.png

A related topic is:

"Pretty Wild Narcissistic Numbers - Numbers that pwn", http://www.tri.org.au/numQ/pwn/

and a paper I wrote on the radical case:

Rose, C (2005), "Radical Narcissistic Numbers", Journal of Recreational Mathematics, 33(4), 2004-2005, 250-254

which also contains references to related literature.