This is a famous problem from 1882, to which a prize of $1000 was awarded for the best solution.
The task is to arrange the seven numbers 4, 5, 6, 7, 8, 9, and 0, and eight dots, in such a way that an addition of two or more numbers approximates 82 as closely as possible.
Each of the numbers can be used only once.
The dots can be used in two ways: as decimal point and as symbol for a recurring decimal.
For example, the fraction 1/3 can be written as:
.
. 3
The dot on top of the three denotes that this digit is repeated infinitely. If a group of numbers needs to be repeated, two dots are used: one to denote the beginning of the recurring part and one to denote the end of it. For example, the fraction 1/7 can be written as:
. .
. 1 4 2 8 5 7
(Note that '0.5' is written as '.5'.)
How close can you get to the number 82?
(In reply to
re: even closer... by Charlie)
Well, by avoiding going through all those permutations, I got a program written, anticlimactically after the solution was found manually.
The program doesn't count the dots, but there are not that many solutions that add to 82, so the ones with 8 dots can be picked out manually. The output shows the ordinary decimal points, plus a dot before a repetition, and after a repetition of more than one digit. The total is shown, and sometimes due to internal rounding, it does not seem to be exactly 82, but it is:
80.4.6 ..5 .9.7 82
80..46. ..5 ..97. 82
80.6.4 ..5 .7.9 82
80..64. ..5 ..79. 82
80.4.7 ..5 .9.6 82.00000000000001
80..47. ..5 ..96. 82
80.7.4 ..5 .6.9 82.00000000000001
80..74. ..5 ..69. 82.00000000000001
80..5 .4.6 .9.7 82
80..5 ..46. ..97. 82
80..5 .6.4 .7.9 82
80..5 ..64. ..79. 82
80..5 .4.7 .9.6 82
80..5 ..47. ..96. 82
80..5 .7.4 .6.9 82
80..5 ..74. ..69. 82.00000000000001
80.6.9 .7.4 ..5 81.99999999999999
80..69. ..74. ..5 82.00000000000001
80.9.6 .4.7 ..5 82
80..96. ..47. ..5 82
80.7.9 .6.4 ..5 82
80..79. ..64. ..5 82
80.9.7 .4.6 ..5 82.00000000000001
80..97. ..46. ..5 82
80 .4.6 ..5 .9.7 82
80 ..46. ..5 ..97. 82
80 .6.4 ..5 .7.9 82
80 ..64. ..5 ..79. 82
80 .4.7 ..5 .9.6 82
80 ..47. ..5 ..96. 82
80 .7.4 ..5 .6.9 82
80 ..74. ..5 ..69. 82.00000000000001
-------
These are the same results Tristan got manually, with the fractions shuffled among the three addends. The ones with only 6 dots in fact merely have a single digit after the decimal and a single repeated digit after that.
The program:
DECLARE SUB groupEm (avail$)
DECLARE SUB buildOn (avail$)
DECLARE SUB examine (g#)
DECLARE SUB permute (a$)
DEFDBL A-Z
CLEAR , , 4000
dig$ = "0456789"
DIM SHARED grps AS INTEGER
DIM SHARED grp$(10), hist$(10), valHist(10), perm(10)
DIM SHARED minDots, maxDots, totValue
OPEN "dots.txt" FOR OUTPUT AS #2
perm(1) = 1
FOR i = 2 TO 10
perm(i) = i * perm(i - 1)
NEXT
grps = 0: totValue = 0
groupEm dig$
CLOSE
END
SUB buildOn (avail$)
STATIC ct
IF avail$ = "" THEN
ct = ct + 1
PRINT ct; " ";
FOR i = 1 TO grps
PRINT grp$(i); " ";
NEXT
PRINT
minDots = 0: maxDots = 0: totValue = 0
examine 1
' IF ct / 40 = INT(ct / 40) THEN DO: LOOP UNTIL INKEY$ > ""
ELSE
groupEm avail$
IF LEN(avail$) > 3 - grps THEN
FOR i = 1 TO LEN(avail$)
ch$ = MID$(avail$, i, 1)
IF ch$ > RIGHT$(grp$(grps), 1) THEN
grp$(grps) = grp$(grps) + ch$
av2$ = LEFT$(avail$, i - 1) + MID$(avail$, i + 1)
buildOn av2$
grp$(grps) = LEFT$(grp$(grps), LEN(grp$(grps)) - 1)
END IF
NEXT
END IF
END IF
END SUB
SUB examine (g)
gr$ = grp$(g)
l = LEN(gr$)
FOR p = 1 TO perm(l)
FOR decimal = 0 TO l
FOR begrept = 0 TO decimal
iPart$ = LEFT$(gr$, l - decimal)
valHist(g) = VAL(iPart$)
n1$ = ""
n2$ = ""
IF decimal > 0 THEN
n1$ = MID$(gr$, l - decimal + 1, decimal - begrept)
num1 = VAL(n1$)
den1 = VAL(LEFT$("100000000", decimal - begrept + 1))
valHist(g) = valHist(g) + num1 / den1
IF begrept > 0 THEN
n2$ = MID$(gr$, l - begrept + 1)
num2 = VAL(n2$)
den2 = VAL(LEFT$("999999999", begrept))
valHist(g) = valHist(g) + num2 / (den2 * den1)
END IF
END IF
hist$(g) = iPart$
IF n1$ > "" OR n2$ > "" THEN hist$(g) = hist$(g) + "." + n1$
IF n2$ > "" THEN hist$(g) = hist$(g) + "." + n2$
IF LEN(n2$) > 1 THEN hist$(g) = hist$(g) + ". "
tValSave = totValue
totValue = totValue + valHist(g)
IF g < grps THEN
IF totValue < 83 THEN
examine g + 1
END IF
ELSE
IF ABS(totValue - 82) < .001 THEN
FOR i = 1 TO grps
PRINT hist$(i); \" \";
PRINT #2, hist$(i); \" \";
NEXT
PRINT \" \"; totValue
PRINT #2, \" \"; totValue
END IF
END IF
totValue = tValSave
NEXT begrept
NEXT decimal
permute gr$
NEXT p
END SUB
SUB groupEm (avail$)
grps = grps + 1
grp$(grps) = LEFT$(avail$, 1)
av2$ = MID$(avail$, 2)
buildOn av2$
grps = grps - 1
END SUB
DEFSNG A-Z
SUB permute (a$)
DEFINT A-Z
x$ = \"\"
FOR i = LEN(a$) TO 1 STEP -1
l$ = x$
x$ = MID$(a$, i, 1)
IF x$ < l$ THEN EXIT FOR
NEXT
IF i = 0 THEN
FOR j = 1 TO LEN(a$) \ 2
x$ = MID$(a$, j, 1)
MID$(a$, j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
MID$(a$, LEN(a$) - j + 1, 1) = x$
NEXT
ELSE
FOR j = LEN(a$) TO i + 1 STEP -1
IF MID$(a$, j, 1) > x$ THEN EXIT FOR
NEXT
MID$(a$, i, 1) = MID$(a$, j, 1)
MID$(a$, j, 1) = x$
FOR j = 1 TO (LEN(a$) - i) \ 2
x$ = MID$(a$, i + j, 1)
MID$(a$, i + j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
MID$(a$, LEN(a$) - j + 1, 1) = x$
NEXT
END IF
END SUB
|
|
Posted by Charlie
on 2003-12-25 01:37:02 |
re(2): even closer...
