The numbers 36 onward all need the factorial in their representation, as do 26, 29, 31 and 34. Most of the number have several representations; I've selected those with the fewest !'s. The left column contains Reverse Polish Notation, and the right column shows the algebraic notation. First 1 through 100:
1,2,3,4,5-+/* 1 1 1*2/(3+4-5)
3,4,2+/,5,1-* 2 2 (3/(4+2))*(5-1)
1,2,3,4-/,5+* 3 3 1*(2/(3-4)+5)
4,5,3,1*-/,2+ 4 4 4/(5-3*1)+2
1,2,3,4-+/,5* 5 5 (1/(2+3-4))*5
3,1/,5-,4,2*+ 6 6 3/1-5+4*2
3,2*,5,1-,4/+ 7 7 3*2+(5-1)/4
1,5,4,2/*+,3- 8 8 1+5*4/2-3
5,3,1/,2-*,4+ 9 9 5*(3/1-2)+4
5,3,1/-,2,4*+ 10 10 5-3/1+2*4
3,4,2/,5,1-*+ 11 11 3+(4/2)*(5-1)
4,3-,1/,5+,2* 12 12 ((4-3)/1+5)*2
4,1/,2+,3*,5- 13 13 (4/1+2)*3-5
5,3,1-+,4*,2/ 14 14 (5+3-1)*4/2
1,5+,3,2,4/-* 15 15 (1+5)*(3-2/4)
4,2-,5,1/,3+* 16 16 (4-2)*(5/1+3)
3,5*,4+,2-,1/ 17 17 (3*5+4-2)/1
4,2/,5+,1-,3* 18 18 (4/2+5-1)*3
1,3-,2/,5,4*+ 19 19 (1-3)/2+5*4
1,5+,4,2,3/-* 20 20 (1+5)*(4-2/3)
5,4,2-+,3*,1/ 21 21 (5+4-2)*3/1
5,3,2/+,1-,4* 22 22 (5+3/2-1)*4
5,4*,3+,2,1-/ 23 23 (5*4+3)/(2-1)
5,2,3,1-/+,4* 24 24 (5+2/(3-1))*4
4,3+,2-,1/,5* 25 25 ((4+3-2)/1)*5
3!,5,4+*,2/,1- 26 26 3!*(5+4)/2-1
5,4+,3*,2,1-/ 27 27 (5+4)*3/(2-1)
5,1,3/-,4,2+* 28 28 (5-1/3)*(4+2)
1,5!*,4/,3-,2+ 29 29 1*5!/4-3+2
3,5,1/+,4*,2- 30 30 (3+5/1)*4-2
1,3*,2-,5!,4/+ 31 31 1*3-2+5!/4
3,2,1-/,5+,4* 32 32 (3/(2-1)+5)*4
5,4,3+*,2-,1/ 33 33 (5*(4+3)-2)/1
4,5,3,2,1-/!*+ 34 34 4+5*(3/(2-1))!
3,4,2,1-/+,5* 35 35 (3+4/(2-1))*5
3,4!*,5,1,2+-/ 36 36 3*4!/(5-(1+2))
4,1/!,2-,3,5*+ 37 37 (4/1)!-2+3*5
2,5+,3,1/!*,4- 38 38 (2+5)*(3/1)!-4
3!,5,4,1-,2/+* 39 39 3!*(5+(4-1)/2)
2,4,1+,3/-,5!* 40 40 (2-(4+1)/3)*5!
2,5,4!*,3/+,1- 41 41 2+5*4!/3-1
5!,1,4+/,3-,2* 42 42 (5!/(1+4)-3)*2
5,2,4!+*,1-,3/ 43 43 (5*(2+4!)-1)/3
3,5-,4!+,1/,2* 44 44 ((3-5+4!)/1)*2
2,1,3/-,4!*,5+ 45 45 (2-1/3)*4!+5
2,4!,1/*,3,5-+ 46 46 2*4!/1+3-5
4!,3,1/-,2*,5+ 47 47 (4!-3/1)*2+5
4,5,1,3+-/!,2* 48 48 (4/(5-(1+3)))!*2
2,4!,1,5,3-/+* 49 49 2*(4!+1/(5-3))
2,1/,4!,5,3-*+ 50 50 2/1+4!*(5-3)
4!,5,2+-,3*,1/ 51 51 (4!-(5+2))*3/1
3,1/!,5,4+*,2- 52 52 (3/1)!*(5+4)-2
4!,5,2/+,3,1-* 53 53 (4!+5/2)*(3-1)
5,4+,3,2,1-/!* 54 54 (5+4)*(3/(2-1))!
5,2+,4!,3/*,1- 55 55 (5+2)*4!/3-1
5!,4/,3-,1+,2* 56 56 (5!/4-3+1)*2
3,5!,4,2+/,1-* 57 57 3*(5!/(4+2)-1)
1,2,5!,4/*,3-+ 58 58 1+2*5!/4-3
2,4,1/!,5-,3*+ 59 59 2+((4/1)!-5)*3
5!,4/,3,1+,2-* 60 60 (5!/4)*(3+1-2)
4,1,3*-,5!,2/+ 61 61 4-1*3+5!/2
4!,5,3/,1+*,2- 62 62 4!*(5/3+1)-2
4,1/!,2+,5-,3* 63 63 ((4/1)!+2-5)*3
4,3,2/,1-,5!*+ 64 64 4+(3/2-1)*5!
4!,3+,1-,5*,2/ 65 65 (4!+3-1)*5/2
3,5!,4,1+/,2-* 66 66 3*(5!/(4+1)-2)
4!,5,3/-,2,1+* 67 67 (4!-5/3)*(2+1)
5!,2/,3,1-,4*+ 68 68 5!/2+(3-1)*4
3,1/,4!*,2+,5- 69 69 (3/1)*4!+2-5
3,1,4+!*,5/,2- 70 70 3*(1+4)!/5-2
4!,2,1/-,3*,5+ 71 71 (4!-2/1)*3+5
3,5!,4,2,1-+/* 72 72 3*5!/(4+2-1)
2,4,1/!+,3*,5- 73 73 (2+(4/1)!)*3-5
5!,3/,4-,1+,2* 74 74 (5!/3-4+1)*2
4!,3,1/*,5+,2- 75 75 4!*3/1+5-2
4,3!,5,1-!*,2/+ 76 76 4+3!*(5-1)!/2
2,5!*,3/,4-,1+ 77 77 2*5!/3-4+1
3,4!,5,1-,2/+* 78 78 3*(4!+(5-1)/2)
1,2,5!*+,4-,3/ 79 79 (1+2*5!-4)/3
5,2,3/,1+-,4!* 80 80 (5-(2/3+1))*4!
3,4!,5,2,1/-+* 81 81 3*(4!+5-2/1)
5!,3+,2,4,1-/* 82 82 (5!+3)*2/(4-1)
2,4,1-/,5!*,3+ 83 83 (2/(4-1))*5!+3
4!,2,5+*,3,1-/ 84 84 4!*(2+5)/(3-1)
3,4!,1/,5+*,2- 85 85 3*(4!/1+5)-2
3,1+!,5,2/-,4* 86 86 ((3+1)!-5/2)*4
4!,5,3/,2+*,1- 87 87 4!*(5/3+2)-1
4!,2/,1-,5,3+* 88 88 (4!/2-1)*(5+3)
5!,4/,3*,1,2-+ 89 89 (5!/4)*3+1-2
4,1-,2*!,3,5+/ 90 90 ((4-1)*2)!/(3+5)
3,1,5!,4/+*,2- 91 91 3*(1+5!/4)-2
5,3+,2/,4!,1-* 92 92 ((5+3)/2)*(4!-1)
2,1-,5!,4/+,3* 93 93 (2-1+5!/4)*3
5!,3!,4*,2+,1/- 94 94 5!-(3!*4+2)/1
3,2+!,4,5/*,1- 95 95 (3+2)!*4/5-1
4!,5,3-,1/,2+* 96 96 4!*((5-3)/1+2)
1,5!+,3!,2/!,4*- 97 97 1+5!-(3!/2)!*4
4,1+,5!,3!/*,2- 98 98 (4+1)*5!/3!-2
5!,1,2/,4-,3!*+ 99 99 5!+(1/2-4)*3!
3,2,1/+!,4,5*- 100 100 (3+2/1)!-4*5
For zero, a couple of examples are given in the puzzle itself. Here's a sampling of the 876 found for zero:
((1+2-3)/4)*5
((1+2-3)/5)*4
((1+3-4)/2)*5
((1+3-4)/5)*2
((1+4-5)/2)*3
((1+4-5)/3)*2
((1+5)/2-3)*4
((1+5)/3)*2-4
((1+5)/3-2)*4
((1+5)/4)*2-3
((1-3)*2+4)/5
((1-3+2)/4)*5
((1-3+2)/5)*4
((1-4+3)/2)*5
((1-4+3)/5)*2
((1-5+4)/2)*3
((1-5+4)/3)*2
((2+1-3)/4)*5
((2+1-3)/5)*4
((2+3)*1-5)/4
((2+3)/1-5)*4
((2+3)/5-1)*4
((2+3-5)/1)*4
((2+3-5)/4)*1
((2-3+1)/4)*5
((2-3+1)/5)*4
((2-5)*1+3)/4
((2-5)/1+3)*4
((2-5)/3+1)*4
((2-5+3)/1)*4
((2-5+3)/4)*1
((3+1-4)/2)*5
((3+1-4)/5)*2
((3+2)*1-5)/4
((3+2)/1-5)*4
((3+2)/5-1)*4
((3+2-5)/1)*4
((3+2-5)/4)*1
((3+5)/2)*1-4
((3+5)/2-4)*1
((3+5)/4)*1-2
((3+5)/4-2)*1
((3-(1+2))/4)*5
((3-(1+2))/5)*4
((3-(2+1))/4)*5
((3-(2+1))/5)*4
((3-4+1)/2)*5
((3-4+1)/5)*2
((3-5)*1+2)/4
((3-5)*2+4)/1
((3-5)/1)*2+4
((3-5)/1+2)*4
((3-5)/2+1)*4
((3-5)/4)*2+1
((3-5+2)/1)*4
((3-5+2)/4)*1
((4+1-5)/2)*3
((4+1-5)/3)*2
((4-(1+3))/2)*5
((4-(1+3))/5)*2
((4-(3+1))/2)*5
((4-(3+1))/5)*2
((4-5+1)/2)*3
((4-5+1)/3)*2
((5+1)/2-3)*4
((5+1)/3)*2-4
((5+1)/3-2)*4
((5+1)/4)*2-3
((5+3)/2)*1-4
((5+3)/2-4)*1
((5+3)/4)*1-2
((5+3)/4-2)*1
(2*(1-3)+4)/5
(2*(3-5)+4)/1
(2*1+3-5)/4
(2*1-5+3)/4
(2*3-(1+5))/4
(2*3-(5+1))/4
(2*4-(3+5))/1
(2*4-(5+3))/1
(2+(3-5)*1)/4
(2+(3-5)/1)*4
(2+1*(3-5))/4
(2+1*3-5)/4
(2+1-3)*4/5
(2+1-3)*5/4
(2+1-3)/4*5
(2+1-3)/5*4
(2+3*1-5)/4
(2/3)*(1+4-5)
(2/3)*(1+5)-4
(2/3)*(1-5+4)
(2/3)*(4+1-5)
(2/3)*(4-5+1)
(2/3)*(5+1)-4
(2/3)*(5-(1+4
(2/3)*(5-(4+1
(2/4)*(1+5)-3
(2/4)*(3-5)+1
(2/4)*(5+1)-3
(2/5)*(1+3-4)
(2/5)*(1-4+3)
(2/5)*(3+1-4)
(2/5)*(3-4+1)
(2/5)*(4-(1+3
(2/5)*(4-(3+1
(3*1+2-5)/4
(3*1+5)/2-4
(3*1+5)/4-2
(3*1-5+2)/4
(3*2-(1+5))/4
(3*2-(5+1))/4
(3+(2-5)*1)/4
(3+(2-5)/1)*4
(3+1*(2-5))/4
(3+1*2-5)/4
(3+1*5)/2-4
(3+1*5)/4-2
(3+1-4)*2/5
(3+1-4)*5/2
(3+1-4)/2*5
(3+1-4)/5*2
(3+2*1-5)/4
(3+2-1*5)/4
(3+2-5)*1/4
(3+2-5)*4/1
(3+2-5)/1*4
(3+2-5)/4*1
(3+2-5*1)/4
(3+2-5/1)*4
(3+2/1-5)*4
(3+4/2)*1-5
(3+4/2-5)*1
(3+5)*1/2-4
(3+5)*1/4-2
(3+5)/1*2-4
(3+5)/1*4-2
(3+5)/1-2*4
(3+5)/1-4*2
(3+5)/2*1-4
(3+5)/2*4-1
(3+5)/2-1*4
(3+5)/2-4*1
3*(1+4-5)/2
3*(1-5+4)/2
3*(4+1-5)/2
3*(4-5+1)/2
3*(5-(1+4))/2
3*(5-(4+1))/2
3*1+4/2-5
3*1-5+4/2
An interesting challenge is to find the first number that's not expressible this way. It lies within the range 101-200 (three numbers in that range are not expressible in the confines of the problem).
The program for 1-100 follows; the one for zero is similar. The output is RPN only; a separate program converted RPN to algebraic notation:
DECLARE FUNCTION fact& (x&)
DEFLNG A-Z
DECLARE SUB try ()
CLEAR , , 25000
OPEN "0-100f.txt" FOR OUTPUT AS #2
DIM SHARED noNums, no8s, noOps, stack#(30), lvl
DIM SHARED stacksize, f$, ctSol, hlvl, used(5), avail$
avail$ = "+-*/"
f$ = "": noNums = 0: stacksize = 0: no8s = 0: noOps = 0
FOR i = 1 TO 5
f$ = LTRIM$(STR$(i))
noNums = 1
used(i) = 1
stacksize = 1
stack#(1) = i
no8s = 1
noOps = 0
try
used(i) = 0
NEXT
CLOSE
PRINT ctSol
FUNCTION fact (x)
t = 1
FOR i = 2 TO x
t = t * i
NEXT
fact = t
END FUNCTION
SUB try
lvl = lvl + 1
IF lvl > hlvl THEN hlvl = lvl: PRINT lvl, f$
IF no8s < 5 THEN
FOR tNo = 1 TO 5
IF used(tNo) = 0 THEN
used(tNo) = 1
f$ = f$ + "," + LTRIM$(STR$(tNo))
stacksize = stacksize + 1
stack#(stacksize) = tNo
no8s = no8s + 1
try
f$ = LEFT$(f$, LEN(f$) - 2)
stacksize = stacksize - 1
no8s = no8s - 1
used(tNo) = 0
END IF
NEXT tNo
END IF
dontFact = 0
IF LEN(f$) > 3 THEN
IF RIGHT$(f$, 2) = "!!" THEN dontFact = 1
END IF
IF stack#(stacksize) <= 12 AND stack#(stacksize) >= 0 AND dontFact = 0 THEN
f$ = f$ + "!"
ssSave# = stack#(stacksize)
IF ssSave# = INT(ssSave#) AND ssSave# > 2 THEN
arg = ssSave#
stack#(stacksize) = fact(arg)
try
END IF
f$ = LEFT$(f$, LEN(f$) - 1)
stack#(stacksize) = ssSave#
END IF
IF stacksize > 1 THEN
h2# = stack#(stacksize)
stacksize = stacksize - 1
h1# = stack#(stacksize)
ix = INSTR(avail$, "+")
IF ix THEN
avail$ = LEFT$(avail$, ix - 1) + MID$(avail$, ix + 1)
stack#(stacksize) = h1# + h2#
f$ = f$ + "+"
try
f$ = LEFT$(f$, LEN(f$) - 1)
avail$ = avail$ + "+"
END IF
ix = INSTR(avail$, "-")
IF ix THEN
avail$ = LEFT$(avail$, ix - 1) + MID$(avail$, ix + 1)
stack#(stacksize) = h1# - h2#
f$ = f$ + "-"
try
f$ = LEFT$(f$, LEN(f$) - 1)
avail$ = avail$ + "-"
END IF
ix = INSTR(avail$, "*")
IF ix THEN
avail$ = LEFT$(avail$, ix - 1) + MID$(avail$, ix + 1)
IF h1# = 0 OR h2# = 0 THEN
tst = 1
ELSE
tst = (LOG(ABS(h1#)) + LOG(ABS(h2#))) / LOG(10)
END IF
IF tst < 300 THEN
stack#(stacksize) = 1# * h1# * h2#
f$ = f$ + "*"
try
f$ = LEFT$(f$, LEN(f$) - 1)
END IF
avail$ = avail$ + "*"
END IF
ix = INSTR(avail$, "/")
IF ix THEN
avail$ = LEFT$(avail$, ix - 1) + MID$(avail$, ix + 1)
IF h2# <> 0 THEN
stack#(stacksize) = h1# / h2#
f$ = f$ + "/"
try
f$ = LEFT$(f$, LEN(f$) - 1)
END IF
avail$ = avail$ + "/"
END IF
stack#(stacksize) = h1#
stacksize = stacksize + 1
stack#(stacksize) = h2#
ELSE
IF no8s = 5 AND avail$ = "" AND stacksize = 1 THEN
solt# = INT(stack#(1) + .5)
IF stack#(1) <> 0 AND ABS(stack#(1)) < 101 THEN
IF ABS(ABS(solt# / stack#(1)) - 1) < 1E-08 THEN
PRINT USING "\ \ #### ###"; f$; stack#(1); ABS(stack#(1))
PRINT #2, USING "\ \ #### ###"; f$; stack#(1); ABS(stack#(1))
ctSol = ctSol + 1
PRINT ctSol
END IF
END IF
END IF
END IF
lvl = lvl - 1
EXIT SUB
END SUB
|
|
Posted by Charlie
on 2005-10-29 14:02:18 |
computer solution -- minimum use of factorial
