+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: an interesting problem (/thread-3769.html)
an interesting problem - Don Shepherd - 05-02-2015 08:37 PM
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.
RE: an interesting problem - Gerald H - 05-02-2015 09:05 PM
Are you sure you want the minimum number you must check? Don't you mean the maximum you must check?
RE: an interesting problem - Don Shepherd - 05-02-2015 09:53 PM
(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?
RE: an interesting problem - TASP - 05-02-2015 11:27 PM
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.
RE: an interesting problem - Don Shepherd - 05-02-2015 11:44 PM
(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 ....
RE: an interesting problem - RayAtHP - 05-03-2015 12:01 AM
Via a karnaugh veitch diagram / map?
RE: an interesting problem - Gerson W. Barbosa - 05-03-2015 12:28 AM
No solution found after testing 24 numbers.
Gerson.
RE: an interesting problem - Don Shepherd - 05-03-2015 12:33 AM
(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.
RE: an interesting problem - Gerson W. Barbosa - 05-03-2015 12:42 AM
(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 :-)
RE: an interesting problem - Don Shepherd - 05-03-2015 01:50 AM
I forgot to mention another restriction on the 3-digit number: it must contain 3 unique digits, that is, no repeating digits.
RE: an interesting problem - Gerson W. Barbosa - 05-03-2015 02:29 AM
(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 :-)
RE: an interesting problem - Paul Dale - 05-03-2015 03:10 AM
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
379For 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
973So twenty four possibilities here. However by judiciously choosing composite numbers first, we can do it in with four tries
Code:
371
319
791
793More 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
RE: an interesting problem - Gerson W. Barbosa - 05-03-2015 03:51 AM
(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
971917 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.
RE: an interesting problem - Paul Dale - 05-03-2015 05:07 AM
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: ENDRE: an interesting problem - Paul Dale - 05-03-2015 05:09 AM
This program checks twenty number for primality on a complete run.
This is worse than it could be due to the fives issue.
- Pauli
RE: an interesting problem - Thomas Klemm - 05-03-2015 05:42 AM
(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
RE: an interesting problem - Don Shepherd - 05-03-2015 06:49 AM
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.
RE: an interesting problem - Gerson W. Barbosa - 05-03-2015 03:23 PM
(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!
RE: an interesting problem - Don Shepherd - 05-03-2015 04:21 PM
(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
RE: an interesting problem - Joe Horn - 05-04-2015 02:23 PM
(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...