an interesting problem

[Don Shepherd]

Does there exist a 3-digit integer such that all 3-digit combinations of those 3 digits are prime numbers? What is the minimum number of numbers you would have to check to answer this question?

I'm not looking for a program for this, just some basic logic.

[Gerald H]

Are you sure you want the minimum number you must check? Don't you mean the maximum you must check?

[Don Shepherd]

(05-02-2015 09:05 PM)Gerald H Wrote:  Are you sure you want the minimum number you must check? Don't you mean the maximum you must check?

Yes, you're right, what is the maximum number of numbers you must check?

[TASP]

It won't be an even number.




I just blew out 1/2 the possibilities, no one else can pare down the list as much as I just did.

[Don Shepherd]

(05-02-2015 11:27 PM)TASP Wrote:  no one else can pare down the list as much as I just did.

I wouldn't be so sure ....

[RayAtHP]

Via a karnaugh veitch diagram / map?

[Gerson W. Barbosa]

No solution found after testing 24 numbers.

Gerson.

[Don Shepherd]

(05-03-2015 12:28 AM)Gerson W. Barbosa Wrote:  No solution found after testing 24 numbers.

Gerson.

Ah, Gerson, I can never fool you. 24 was the number, and you are correct, no solutions.

[Gerson W. Barbosa]

(05-03-2015 12:33 AM)Don Shepherd Wrote:  

(05-03-2015 12:28 AM)Gerson W. Barbosa Wrote:  No solution found after testing 24 numbers.

Gerson.

Ah, Gerson, I can never fool you. 24 was the number, and you are correct, no solutions.

I would've said 22, but I didn't want to mislead anybody. I already knew 179 and 197 were both primes :-)

[Don Shepherd]

I forgot to mention another restriction on the 3-digit number: it must contain 3 unique digits, that is, no repeating digits.

[Gerson W. Barbosa]

(05-03-2015 01:50 AM)Don Shepherd Wrote:  I forgot to mention another restriction on the 3-digit number: it must contain 3 unique digits, that is, no repeating digits.

Somehow I've assumed that restriction despite there was no reason to do so, which makes my quick solution completely wrong. In that case 113, 131 and 311 would be one solution. I will pay more attention next time :-)

[Paul Dale]

There can't be an even digit (or zero) since putting that digit in the final position results in a composite number. Likewise, we can't have a five. That leaves: 1, 3, 7 & 9 as possible digits.

Since we're not allowed repeated digits we have to check:

Code:

137
139
179
379

For each of these four we need to check all digit permutations:

Code:

137
173
317
371
713
731

139
193
319
391
913
931

179
197
719
791
917
971

379
397
739
793
937
973

So twenty four possibilities here. However by judiciously choosing composite numbers first, we can do it in with four tries

Code:

371
319
791
793

More realistically, by starting at the top of each list of six and stopping when we find a composite, we have to make fifteen primality checks.

- Pauli

[Gerson W. Barbosa]

(05-03-2015 03:10 AM)Paul Dale Wrote:  More realistically, by starting at the top of each list of six and stopping when we find a composite, we have to make fifteen primality checks.

- Pauli

This is one of my lists:

Code:


179
197
719
917
791
971

917 is the first composite, but the WP 34S PRIME? test is a joy to use, so much I would not stop until I had tested them all :-)

Gerson.

[Paul Dale]

For fun here is a 34S program to solve this problem, albeit not optimally since it doesn't exclude fives. Runs virtually instantly. I'm sure there are a lot of space savings to be had here and probably some algorithmic ones too.

- Pauli

Code:

01:  LBL A
02:  1
03:  .
04:  0
05:  0
06:  9
07:  0
08:  2
09:  +/-
10:  STO 00
11:  LBL 00
12:  ISG 00
13:  GTO 01
14:  RTN
15:  LBL 01
16:  RCL 00
17:  STO 01
18:  LBL 11
19:  ISG 01
20:  GTO 02
21:  GTO 00
22:  LBL 02
23:  RCL 01
24:  STO 02
25:  LBL 12
26:  ISG 02
27:  GTO 03
28:  GTO 11
29:  LBL 03
30:  RCL 00
31:  IP
32:  RCL 01
33:  IP
34:  RCL 02
35:  IP
36:  XEQ 20    
37:  GTO 12
38:  x<> Y
39:  XEQ 20    
40:  GTO 12
41:  <-> ZYXT
42:  XEQ 20    
43:  GTO 12
44:  x<> Y
45:  XEQ 20    
46:  GTO 12
47:  <-> ZYXT
48:  XEQ 20
49:  GTO 12
50:  x<> Y    
51:  XEQ 20
52:  GTO 12
53:  XEQ 30
54:  PSE 20
55:  GTO 12
56:  LBL 20
57:  XEQ 30
58:  PRIME?
59:  GTO 21
60:  RTN
61:  LBL 21
62:  DROP
63:  RTN+1
64:  LBL 30
65:  #100    
66:  RCL *T    
67:  #10    
68:  RCL *T    
69:  +    
70:  RCL+ Y    
71:  END

[Paul Dale]

This program checks twenty number for primality on a complete run.
This is worse than it could be due to the fives issue.


- Pauli

[Thomas Klemm]

(05-03-2015 03:10 AM)Paul Dale Wrote:  More realistically, by starting at the top of each list of six and stopping when we find a composite, we have to make fifteen primality checks.

By using the divisibilty rule by 7 we have to make 20 checks:

137 -1
173 11
317 17
371 35
713 65
731 71

139 -5
193 13
319 13
391 37
913 85
931 91

179 -1
197 5
719 53
791 77
917 77
971 95

379 19
397 25
739 55
793 73
937 79
973 91

But then the check needs only a little mental arithmetic.
By rearranging the numbers so that the first digit is last we have to make only 6 checks:

371 35
731 71
173 11
713 65
137 -1
317 17

391 37
931 91
193 13
913 85
139 -5
319 13

791 77
971 95
197 5
917 77
179 -1
719 53

793 73
973 91
397 25
937 79
379 19
739 55


Cheers
Thomas

[Don Shepherd]

Thanks to all who participated.

I should have stated the restriction regarding duplicate digits in my original post. Gerson, however, read my mind. I couldn't fall asleep last night (tonight!) thinking that I had omitted something, then I realized it was no duplicate digits allowed.

The maximum number of checks depends entirely on the order of the 6 entries in each of 4 lists: the 137 list, 139 list, the 379 list, and the 971 list. The best case is 4, as Pauli said, assuming you choose a composite number as the first member of each list. The worst case, it seems to me, would be 17, assuming you find all of the primes first in each list [3 primes in the 137 list, 2 primes in the 139 list, 4 primes in the 379 list, and 4 primes in the 971 list means tries = (3+1) + (2+1) + (4+1) + (4+1) = 17]. In my actual case, it was 12, but I went on and checked the remaining 12 numbers for primality too.

Interestingly (to me at least, but then I'm weird), if we evaluate this for a 4-digit number instead of a 3-digit number, the number of permutations is the same [P(4,4)=24] and there is no solution as well.

[Gerson W. Barbosa]

(05-03-2015 06:49 AM)Don Shepherd Wrote:  Interestingly (to me at least, but then I'm weird), if we evaluate this for a 4-digit number instead of a 3-digit number, the number of permutations is the same [P(4,4)=24] and there is no solution as well.

This appears to be a matter of probability. Sure there are about 1050 4-digit prime numbers, but in this one only group of 24 numbers it is very unlikely that all of them are primes. But indeed an overall interesting problem. Thanks for submitting it!

[Don Shepherd]

(05-03-2015 03:23 PM)Gerson W. Barbosa Wrote:  in this one only group of 24 numbers it is very unlikely that all of them are primes

Yeah, but it would have been special if one solution was found. Sort of like an odd perfect number. I wonder if someone will find one of those in my lifetime (I'm 64, time is running out ...).

thanks Gerson

[Joe Horn]

(05-03-2015 06:49 AM)Don Shepherd Wrote:  Interestingly (to me at least, but then I'm weird), if we evaluate this for a 4-digit number instead of a 3-digit number, the number of permutations is the same [P(4,4)=24] and there is no solution as well.

How about in hex? We'd need to test up to 8-digit integers then...