Make a list of distinct prime numbers, using the
undecimal digits from 0 to A exactly once each in the list. What is the minimum sum of all the numbers in such a list? What's the minimum product of all the numbers in such a list? (None of the primes may admit leading zeroes).
Note: Think of this problem as an extension of
Pretty Potent Primes.
For minimum sum:
DECLARE FUNCTION from11# (s$)
DECLARE SUB build (n#)
DEFDBL A-Z
OPEN "primbs11.txt" FOR INPUT AS #1
DIM SHARED pr$(400), p(400), h$(12), hist(12), used$, nPrims, minTot
minTot = 99999999
DO
nPrims = nPrims + 1
INPUT #1, pr$(nPrims)
PRINT pr$(nPrims)
p(nPrims) = from11(pr$(nPrims))
LOOP UNTIL EOF(1) OR LEN(pr$(nPrims)) = 3 AND pr$(nPrims) > "240"
CLOSE
build 1
SUB build (n)
IF n = 1 THEN st = 1: ELSE st = hist(n - 1) + 1
FOR i = st TO nPrims
tst$ = pr$(i)
good = 1
FOR j = 1 TO LEN(tst$)
IF INSTR(used$, MID$(tst$, j, 1)) THEN good = 0: EXIT FOR
NEXT
IF good THEN
used$ = used$ + tst$
hist(n) = i
h$(n) = tst$
tot = 0
IF LEN(used$) = 11 THEN
FOR j = 1 TO n
tot = tot + p(hist(j))
NEXT
IF tot <= minTot THEN
FOR j = 1 TO n
PRINT h$(j); " ";
NEXT
minTot = tot
PRINT tot
END IF
ELSE
build n + 1
END IF
used$ = LEFT$(used$, LEN(used$) - LEN(tst$))
END IF
NEXT
END SUB
FUNCTION from11 (s$)
t = 0
FOR i = 1 TO LEN(s$)
t = 11 * t + INSTR("0123456789A", MID$(s$, i, 1)) - 1
NEXT
from11 = t
END FUNCTION
finds
2 + 10 + 3A + 54 + 67 + 89
whose sum in decimal is 285.
For minimum product:
2*3*5*10*47A*689, whose product is 155,077,890 in decimal. This assumes that the largest prime used is no larger than 1561 in base-11 representation, as that is the largest prime on the previously prepared input file of primes in base-11.
DECLARE FUNCTION from11# (s$)
DECLARE SUB build (n#)
DEFDBL A-Z
OPEN "primbs11.txt" FOR INPUT AS #1
DIM SHARED pr$(400), p(400), h$(12), hist(12), used$, nPrims, minProd
minProd = 999999999999#
DO
nPrims = nPrims + 1
INPUT #1, pr$(nPrims)
PRINT pr$(nPrims)
p(nPrims) = from11(pr$(nPrims))
LOOP UNTIL EOF(1)
CLOSE
build 1
SUB build (n)
IF n = 1 THEN st = 1: ELSE st = hist(n - 1) + 1
FOR i = st TO nPrims
tst$ = pr$(i)
good = 1
FOR j = 1 TO LEN(tst$)
IF INSTR(used$, MID$(tst$, j, 1)) THEN good = 0: EXIT FOR
NEXT
IF good THEN
used$ = used$ + tst$
hist(n) = i
h$(n) = tst$
tot = 1
IF LEN(used$) = 11 THEN
FOR j = 1 TO n
tot = tot * p(hist(j))
NEXT
IF tot <= minProd THEN
FOR j = 1 TO n
PRINT h$(j); " ";
NEXT
minProd = tot
PRINT tot
END IF
ELSE
IF tot < minProd / p(hist(n)) THEN
build n + 1
END IF
END IF
used$ = LEFT$(used$, LEN(used$) - LEN(tst$))
END IF
NEXT
END SUB
FUNCTION from11 (s$)
t = 0
FOR i = 1 TO LEN(s$)
t = 11 * t + INSTR("0123456789A", MID$(s$, i, 1)) - 1
NEXT
from11 = t
END FUNCTION
|
|
Posted by Charlie
on 2010-04-14 18:13:09 |
computer solution
