From: tjl@cbnews.cb.att.com (timothy.j.lipetz)
Newsgroups: rec.puzzles
Subject: Four 2s Program (+ assumptions )
Date: 29 Aug 92 18:24:51 GMT
Organization: AT&T



I have written a program to solve the four 2s problem (also
four 4s and four 9s).  Here are solutions for two numbers
previously unreported...
        ________________________________
       /     __     __
      /     /      / _                _
57 = V ( ( V 2  / V .2 ) ! ! + 2 ) / .2

                       _
92 = 2 - ( 2 / ( .2 - .2 ) )

or in the postfix output of my program (where _2 = 2/9) ...
57 = 2 2 sqrt _2 sqrt / ! ! + _2 / sqrt
92 = 2 2 .2 _2 - / -
------------------------------------------------------------------
The problem is that it did not find solutions to several
numbers that were reported.  They are...

    59, 61, 89, 93, 95

Now, I did have to make several simplifying assumptions in order
to reduce the search space enough to make the program practical.
As it is, it runs 15 cpu hours on a Sparc.  (If there is interest
I will post the program and solutions after I clear up the mystery.)

Anyhow, could someone please post the known solutions to the above
five numbers, or alternately tell me which of the following
assumptions made by my program are violated by the solutions.

ASSUMPTIONS:

1) The decimal point and repeating decimal are not generally
applicable operators.  The can only be used in the following ways...
    .2 .22 _2 _22  (where _2 = 2/9 and _22 = 22/99).
I did not feel that we should allow constructions such as...
     ________
    .((2+2)!)  as equal to 24/99

2) I guessed that .222 .2222 _222 _2222 would not prove very
useful.  (Come to think of it, I also left out 2.2 2.22
22.2 2_2 2_22 and 22_2 which might have been useful, but oh boy
would that explode the search space!)

3) I guessed (with some reasoning) that unary negation was not
necessary.  My reasons: we start and end with positive numbers;
the only other operation that produces negatives is subtraction
and the order of its operands could be reversed; and negative
exponentiation merely duplicates division with the positive
exponent.  I know this isn't a proof, but my first estimate
counted over 10 ^ 14 possible expressions, so I had to find
somewhere to cut back.

4) Square roots only apply to numbers greater than 0.

5) Factorial only applies to integers [1..12].  (Since the
program uses floating point (actually doubles), I was worried
about large factorials overflowing.  Does someone know what
the limit is on doubles in the Sparc C compiler?)

6) For X ^ Y, X must be greater than 0.

7) The only unary operations left were ! and R (square root).
I left out the sqare root of any factorial, and also left out
any sub-expression with more that two square roots or two !s.
By combining adjacent unary ops, I came up with this list of
unary ops (in postfix)...
    R  !  R!  RR  !!  RR!  RR!!
Again, I know these are not all possibilities, but my counting
depended on the seventh power of the number of unary ops, so I
really wanted to cut that down.

------------------------------------------------

Anyhow, writing the program was as much fun as solving the
problem the hard way.  (I first worked on the four 4s problem
way back in the mid sixties, when I was in grade school - it
took me over a year to discover the solution to 55.)

Any help on the program would be appreciated.

Thanks,

Timothy J. Lipetz
tjl@cbzoo.att.com
or
att!cbzoo!tjl