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

Home > Numbers
Pretty Potent Primes III (Posted on 2010-04-14) Difficulty: 3 of 5
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.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 1 of 1

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information