All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Numbers and Dots (Posted on 2003-12-24)
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?

 See The Solution Submitted by DJ Rating: 4.2857 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): even closer... | Comment 10 of 12 |
(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

 Search: Search body:
Forums (0)