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

 Pretty Potent Primes (Posted on 2005-03-13)
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?

 See The Solution Submitted by Old Original Oskar! Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 I think I've covered the possibilities--Computer Aided Solution | Comment 4 of 11 |

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     9722       41      53      89      607     7922       41      59      83      607     7922       41      67      83      509     7022       41      67      89      503     7022       47      53      61      809     9722       47      53      89      601     7922       47      59      83      601     7922       47      61      83      509     7022       47      61      89      503     7022       53      67      89      401     6122       59      67      83      401     6125       23      41      67      809     9455       23      41      89      607     7655       23      47      61      809     9455       23      47      89      601     7655       23      67      89      401     585 *5       29      41      83      607     7655       29      47      83      601     7655       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    5242629041      8069    6947409041      8609    74123490461     809     78319290641     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

 Search: Search body:
Forums (0)