Make a list of prime numbers, using the digits from 0 to 9 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?

At first thought, it would seem that using single-digit primes would minimize either of the two: the sum or the product.  However, with single-digit primes 2, 3, 5, 7 used, that leaves only 1 and 9 available to end any other prime numbers to be formed, and with the six digits remaining, the best you can do is 461+809=1270.

Since we do need a three-digit prime (as zero can't be either a leading or a trailing digit), even two-digit primes would not upset the total too much in the attempt to minimize the sum, so we could go with one 1-digit prime, three 2-digit primes and a 3-digit prime with zero in the middle. The possibilities, through exhaustive search, are:

                                       total 
2       41      53      67      809     972
2       41      53      89      607     792
2       41      59      83      607     792
2       41      67      83      509     702
2       41      67      89      503     702
2       47      53      61      809     972
2       47      53      89      601     792
2       47      59      83      601     792
2       47      61      83      509     702
2       47      61      89      503     702
2       53      67      89      401     612
2       59      67      83      401     612
5       23      41      67      809     945
5       23      41      89      607     765
5       23      47      61      809     945
5       23      47      89      601     765
5       23      67      89      401     585 *
5       29      41      83      607     765
5       29      47      83      601     765
5       29      67      83      401     585 *

where 585 is the smallest total, achievable in the two ways marked with an asterisk.

There are no solutions where there are two 1-digit primes, a 2-digit prime and two 3-digit primes.  That leaves 585 as the minimum total.

The program used for the above (with minor modifications to do the 1,1,2,3,3-digit search) is:

   10   Y$="123456789"
   20   for P=1 to !(len(Y$))
   30     gosub *Permute(&Y$)
   40     A=val(mid(Y$,1,1)):B=val(mid(Y$,2,2)):C=val(mid(Y$,4,2))
   41     D=val(mid(Y$,6,2)):E=val(mid(Y$,8,1)+"0"+mid(Y$,9))
   50     if A>0 and B>10 and C>10 and D>10 and E>100 then
   65      :if A>0 and B>A and C>B and D>C and E>D then:
   70     :if nxtprm(A-1)=A and nxtprm(B-1)=B and nxtprm(C-1)=C and nxtprm(D-1)= D and nxtprm(E-1)=E then print A,B,C,D,E,A+B+C+D+E
   80   next
 1000   end
10010
10020    *Permute(&A$)
10025   local X$,I,L$,J
10030     X$=""
10040     for I=len(A$) to 1 step -1
10050      L$=X$
10060      X$=mid(A$,I,1)
10070      if X$<L$ then cancel for:goto 10100
10080     next
10090
10100     if I=0 then
10110     :for J=1 to len(A$)\2
10120     :X$=mid(A$,J,1)
10130     :mid(A$,J,1)=mid(A$,len(A$)-J+1,1)
10140     :mid(A$,len(A$)-J+1,1)=X$
10150     :next
10160     :else
10170     :for J=len(A$) to I+1 step -1
10180     :if mid(A$,J,1)>X$ then cancel for:goto 10200:endif
10190     :next
10200     :mid(A$,I,1)=mid(A$,J,1)
10210     :mid(A$,J,1)=X$
10220     :for J=1 to (len(A$)-I)\2
10230     :X$=mid(A$,I+J,1)
10240     :mid(A$,I+J,1)=mid(A$,len(A$)-J+1,1)
10250     :mid(A$,len(A$)-J+1,1)=X$
10260     :next
10270     :endif
10280    return

For the product portion, though, single-digit primes are in fact better, as, for example, multiplying by 2*3 is better than multiplying by 23, as each digit is less than the factor of 10 that a decimal place costs.

Taking the single-digit primes separately leaves 6 digits remaining. This can't be split up into more than two primes, as a miniumum of three-digit prime is needed for the zero, leaving at most 3 other digits, so one of them would have to be single-digit, but we had already used up the single-digit primes.

An exhaustive search of the allocation of the remaining six digits to two numbers yields

a       b       product (a*b*2*3*5*7)
41      6089    52426290
41      8069    69474090
41      8609    74123490
461     809     78319290
641     809     108899490

leaving the smallest product as 41 * 6089 * 2 * 3 * 5 * 7 = 52426290

Program fragment:

   10   Y$="146890.":Prims=2*3*5*7
   20   for P=1 to !(len(Y$))
   30     gosub *Permute(&Y$)
   40     Ix=instr(Y$,".")
   50     if Ix<>1 and Ix<>len(Y$) then
   55     :if left(Y$,1)<>"0" and mid(Y$,Ix+1,1)<>"0" then
   60     :A=val(left(Y$,Ix-1)):B=val(mid(Y$,Ix+1,*))
   65      :if A>0 and B>A then:
   70     :if nxtprm(A-1)=A and nxtprm(B-1)=B then
   72      :print A,B,A*B*Prims
   80   next
 1000   end
 
 However, if we look for one 6-digit prime instead, then we get a lower product: 104869 * 2 * 3 * 5 * 7 = 22022490.
 
 It would not help to make a 7-digit prime by subsuming the 7 into the large prime, as that would effectively multiply by 10 while dividing by 7, and this is verified by the smallest being 1046897*2*3*5=31406910.

Posted by Charlie on 2005-03-13 17:57:01